- •Міністерство освіти і науки України
- •Математичні моделі економічних задач
- •1.1. Задача планування виробництва
- •1.2. Задача складання раціону (задача про дієту, задача про суміші)
- •1.3. Транспортна задача
- •1.4. Задача про мінімізацію відходів
- •К 2ількість шматків
- •1.5. Задача про призначення
- •Загальна постановка задач лінійного програмування (лп)
- •Перелік питань для самоперевірки
- •Лекція 2
- •Тема 2. Геометрична інтерпретація задач лінійного програмування. Задача лінійного програмування, форми її запису
- •Приведення задачі лп до канонічного виду
- •Приведення задачі лп до симетричного виду
- •Перелік питань для самоперевірки
- •3.1. Визначення вихідного опорного плану
- •3.2. Симплексні таблиці
- •3.3. Поняття про м-метод
- •Перелік питань для самоперевірки
- •Лекція 4
- •Тема 4. Двоїстість у лінійному програмуванні
- •Перелік питань для самоперевірки
- •Лекція 5
- •Тема 5. Методика розв’язування транспортної задачі
- •5.1. Приведення задачі до замкненої форми
- •5.2. Визначення вихідного опорного плану
- •5.3. Метод потенціалів
- •Перелік питань для самоперевірки
- •6.1. Метод відсікань Гоморі
- •Перелік питань для самоперевірки
- •Лекція 6
- •Тема 7. Елементи теорії ігор
- •7.1. Графічний метод
- •7.2. Приведення матричної гри до задачі лінійного програмування
- •Перелік питань для самоперевірки
- •8.2. Задачі нелінійного програмування з нелінійною цільовою функцією та лінійною системою обмежень
- •Перелік питань для самоперевірки
- •Лекція 8
- •Тема 9. Динамічне програмування
- •9.1. Задача про розподіл коштів між підприємствами
- •Рішення
- •9.2. Задача про заміну обладнання
- •Рішення
- •Перелік питань для самоперевірки
- •Список рекомендованої літератури
Приведення задачі лп до канонічного виду
Канонічний вид задачі ЛП:
-
Дано:
Знайти такий план , при якому
.
Задача ЛП представлена в канонічному виді, якщо виконуються наступні умови:
Всі змінні невід’ємні (–умова невід’ємності).
Решта обмежень є лінійними рівняннями.
Функція мети мінімізується .
Будь-яку задачу ЛП можна звести до канонічного виду.
Рекомендації щодо приведення задачі ЛП до канонічного виду
Забезпечення умови невід’ємності змінних:
Якщо на змінну взагалі не накладені ніякі обмеження, то необхідно виконати заміну: де
Якщо на змінну накладено обмеження виду то виконуємо заміну: де
Якщо на змінну накладено обмеження виду то виконуємо заміну: де
Перетворення обмежень-нерівностей у рівняння:
Нерівність заміняємо рівнянням, де
Нерівність заміняємо рівнянням, де
Забезпечення пошуку найменшого значення :
якщо , то
Приведення задачі лп до симетричного виду
Симетричний вид задачі ЛП:
або
Задача ЛП представлена в симетричному виді, якщо виконуються наступні умови:
Умова невід’ємності змінних.
Решта обмежень системи є нерівностями виду „ ≤ ” і функція мети , або решта обмежень системи є нерівностями виду „ ≥ ” і функція мети
Будь-яку задачу ЛП можна звести до симетричного виду.
Рекомендації щодо приведення задачі ЛП до симетричного виду
Дивись рекомендації щодо приведення задачі ЛП до канонічного виду.
Рівняння завжди можна замінити парою нерівностей
Тоді для симетричної постановки
або
Задача 2.2. Наступну задачу лінійного програмування
привести: а) до канонічного виду; б) до симетричного виду.
Рішення
а) Задача ЛП подана в канонічному виді, якщо виконані такі умови:
на кожну змінну накладено умову невід’ємності;
кожне з обмежень подано у виді лінійного рівняння;
функція мети має досягати мінімуму.
Задовольнимо першу умову.
Оскільки на змінну x1 накладено умову , подамо її у виді(де), зміннуx2 – у виді (де), зміннуx3 заміняємо на u3 (), оскількиx4 не має обмежень, подамо її у виді різниці (де,). Підставимо ці співвідношення в систему обмежень і у функцію мети:
(2.1)
Задовольнимо другу умову.
Для того, щоб нерівності записати у виді рівностей, від лівої частини першої нерівності віднімемо нову балансову змінну u60, а до лівої частини другої нерівності додамо балансову змінну u70.
До функції мети змінні u6 і u7 входять з нульовими коефіцієнтами.
Для виконання третьої умови введемо функцію . У результаті одержимо канонічний вид задачі лінійного програмування
б) Використовуючи вигляд (2.1) даної задачі та рекомендації до зведення до симетричного виду, отримуємо
Перелік питань для самоперевірки
Геометричний метод розв’язування задач лінійного програмування з двома змінними, ілюстрація можливих випадків, які трапляються під час розв’язування задачі.
Задача лінійного програмування, форми її запису.
Правила переходу від загальної задачі лінійного програмування до канонічної та симетричної.
Змістовий модуль 2
Методика розв’язування
задач лінійного програмування (ЛП)
Лекція 3
Тема 3. Симплексний метод розв’язання задач ЛП
Симплексний метод є універсальним для розв’язання задачі лінійного програмування.
Схема розв’язання задачі лінійного програмування:
Подати задачу в канонічному виді (всі обмеження математичної моделі, крім умов невід’ємності, мають бути у виді рівностей, функція мети має бути мінімізована).
Знайти вихідний опорний план задачі – початковий допустимий базисний розв’язок системи рівнянь. Базисним називається розв’язок невизначеної системи, у якому вільні змінні дорівнюють нулю, а базисні (після приведення системи до одиничного базису) – відповідним елементам стовпця вільних членів. Базисний розв’язок називається допустимим, якщо всі його компоненти невід’ємні.
З’ясувати, чи є вихідний опорний план оптимальним.
Якщо опорний план не є оптимальний, то побудувати новий опорний план, більш “близький” до оптимального (з меншим значенням функції мети).