Главная | Обратная связь | Поможем написать вашу работу!

Теоретичні відомості

Міністерство освіти і науки, молоді та спорту України

Національний університет “Львівська політехніка”

ПОСТАНОВКА ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

МЕТОДИЧНІ ВКАЗІВКИ

До виконання лабораторної роботи №1

з курсу “ Технології підтримки прийняття рішень ”

для студентів

спеціальності № 8.18010015 - “ Консолідована інформація ”

Затверджено

на засіданні кафедри

соціальних комунікацій

та інформаційної діяльності

Протокол № 12 від 05.04.2012 р.

Львів – 2012

Постановка задач лінійного програмування: Методичні вказівки до виконання лабораторної роботи №1 для студентів освітньо-кваліфікаційного рівня “магістр” спеціальності № 8.18010015 - “Консолідована інформація”. / Укл.: У.Б. Ярка, Т.М.Білущак, 2012. – 9 с.

Укладачі Ярка У.Б., канд. фіз.-мат. наук, доц.

Білущак Т.М., асистент кафедри СКІД

Відповідальна за випуск Пелещишин А.М., д.т.н., доц.

Рецензент доктор фіз.-мат. наук, проф. каф., ОМП Ільків В.С.

Передмова

У методичних вказівках розглянуто загальні етапи в розв'язанні задач математичного програмування.

Методичні вказівки призначені для студентів освітньо-кваліфікаційного рівня “магістр” спеціальності № 8.18010015 - “Консолідована інформація”. і укладені відповідно до робочої програми курсу “Технології підтримки прийняття рішень”.

ЛАБОРАТОРНА РОБОТА № 1

Тема:

Постановка задач лінійного програмування

Мета роботи:

Навчитися будувати математичну модель задач лінійного програмування.

Теоретичні відомості

Прийняття рішень відіграє велику роль у всіх сферах людської діяльності. Для постановки задачі ухвалення рішення необхідно мати дві умови: наявність вибору й наявність принципу, на підставі якого здійснюється вибір варіанта рішення. На ранніх етапах розвитку суспільства доступний обсяг інформації, що використовувалася для прийняття рішень, був невеликий. Тому оптимальне в певному смислі рішення приймалося на підставі інтуїції і досвіду, тобто принципом ухвалення рішення був вольовий вибір. Вольовий вибір часто використовується і сьогодні як єдино можливий при відсутності формалізованих моделей.

Загальні етапи в розв'язанні задач математичного програмування:

1. Побудова математичної моделі задачі – визначення факторів, що вважаються невідомими; побудова системи обмежень; побудова цільової функції на основі умови оптимізації.

2. Вибір методу розв’язку задачі.

3. Коригування математичної моделі.

4. Дослідження отриманого розв’язку і прийняття рішення.

Із зростанням обсягу інформації про досліджуване явище для ухвалення оптимального рішення став використовуватися ряд прямих розрахунків. Розрахунок дає обґрунтування прийнятому рішенню, дозволяє порівнювати рішення за ефективністю. Для порівняння різних варіантів рішення за ефективністю завжди потрібна деяка ознака, що називається критерієм ефективності. Критеріальний вибір полягає у прийнятті певного критерію і порівнянні можливих варіантів за цим критерієм. Варіант, для якого прийнятий критерій приймає найкраще значення, називають оптимальним, а задачу ухвалення найкращого рішення – задачею оптимізації.

Кожна велика система – фінансові чи банківські організації, великі промислові підприємства, військові з’єднання, системи охорони здоров’я, освіти тощо – функціонує заради досягнення певної мети. Усе те, що відбувається в системі, і ступінь досягнення мети, може бути описане математично. І одним з основних інструментів дослідження таких задач (задач оптимізації) є математичне програмування.

Хід роботи

Приклад 1

На меблевій фабриці зі стандартних листів фанери потрібно вирізати необхідну кількість заготовок трьох розмірів. Лист фанери можна розрізати двома способами. Кількість отриманих заготовок та площу відходів за кожного способу розрізування одного листа фанери, а також норми випуску заготовок наведено в таблиці. Скільки листів фанери та за яким способом їх потрібно розрізати, щоб отримати потрібну кількість заготовок з мінімальними відходами?

Наша мета – надати запису задачі математичного змісту, або, як кажуть, скласти її математичну модель. Для цього зручно спочатку записати в таблицю, яка має вигляд:

Заготовки	Кільк. отр. загот. за способ.	Необх. кільк. загот.
А	В



Пл. відх.,см

Почнемо формалізувати задачу. Позначимо кількість отриманих заготовок відповідно за способом А і способом В. Загальна площа відходів см² складає:

(1.1)

Функцію називають цільовою функцією або функцією мети.

На виготовлення кількість отриманих заготівок за способом А і кількість отриманих заготівок за способом В буде визначено:

1-а заготовка - 2-а заготовка - 3-а заготовка

Оскільки є три заготовки, то повинні виконуватися нерівності:

Очевидно, що за змістом задачі величині повинні бути цілі і невід’ємними, тобто

Математичну модель виробничого процесу має вигляд: знайти найменшу цільову функцію (відходи)

(1.2)

Тепер складаємо систему обмежень по кількості заготівок кожного розміру

(1.3) (1.4) (1.5) (1.6)

Розв’язування задачі(1.2)-(1.6) полягає в знаходженні такого розв’язку системи нерівностей(1.3)-(1.6) для якого цільова функція набула б найменшого значення серед усіх її значень на розв’язках цієї системи.

Як видно з побудованої математичної моделі, цільова функція(1.1) і ліва частини (1.3)-(1.6)обмежень є лінійними функціями двох змінних , тому задача(1.2)-(1.6) є задачею лінійного програмування.

Областю допустимих розв’язків задачі називаються множина значень , які задовольняють кожне з обмежень (1.3)-(1.6)

Отже, побудова математичної моделі буде мати такий запис:

Нехай х - кількість листів фанери порізаних 1-м способом;

х₂- кількість листів фанери порізаних 2-м способом.

-цілі

Вимоги до звіту

Звіт повинен містити:

мету роботи.
короткі теоретичні відомості.
опис основних дій, які виконувались протягом лабораторної роботи.
Графічний матеріал у вигляді PrintScreen з відповідними коментарями до всіх пунктів ходу роботи.
Висновки.

Оформлена робота повинна містити верхні та нижні колонтитули, в яких зокрема вказати:

· У верхньому колонтитулі: групу, прізвище та ініціали, назву лабораторної роботи.

· У нижньому колонтитулі: дату створення та нумерацію сторінок.

КОНТРОЛЬНІ ПИТАННЯ

Що називається критерієм ефективності?
Що називається цільовою функцією?

3. Що називається системою обмежень?

4. Що називається допустимою множиною задачі математичного програмування?

5. Що називається областю визначення?

6. Перерахувати загальні етапи в розв'язанні задач математичного програмування?

ЛІТЕРАТУРА:

1. Акулич И.Л. Математическое програмирование в примерах и задачах.-М.: Высш.шк., 1985.

2. Комихман И.С. Сборник задач по математическому програмированию.-М.: Высш.шк., 1975.

3. Ярка У.Б., Білущак Т.М. Методичні вказівки до виконання розрахункових робіт до курсу “Технології підтримки прийняття рішень” для студентів освітньо-кваліфікаційного рівня “магістр” спеціальності
№8.18010015-“Консолідована інформація”.-Львів: Видавництво Національного університету «Львівська політехніка», 2012.

НАВЧАЛЬНЕ ВИДАННЯ