Побудова математичної моделі
Нехай Хj— план виробництва продукціїу-го виду, де у може набувати значень від 1 до 4.
Умовами задачі будуть обмеження на час використання верстатів для виробництва продукції всіх видів:
для верстата 1 
(машино-год);
для верстата 2 
Цільова функція задачі визначається як загальний чистий прибуток від реалізації готової продукції і складається з різниці між ціною та собівартістю виготовлення продукції кожного виду:
Отже, математична модель поставленої задачі має такий вигляд:
Розв'язування. Розв'яжемо задачу симплекс-методом згідно з розглянутим алгоритмом.
1. Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні х5 та х6.
Ці додаткові змінні за економічним змістом означають можливий, але не використаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:
Канонічну систему обмежень задачі запишемо у векторній формі:
де 
Оскільки вектори А5 и А6 та одиничні та лінійно незалежні, саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі х5 та х6 , що відповідають одиничним базисним векторам, називають базисними, а решту вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:
|
|
|
векторна форма запису системи обмежень задач матиме вигляд
Оскільки додатні коефіцієнти х5 та х6 відповідають лінійно незалежним векторам, то за означенням 
є опорним планом задачі і для цього початкового плану
2, Складемо симплексну таблицю для першого опорного плану задачі.
У цій задачі в оцінковому рядку дві оцінки 
та 
суперечать умові оптимальності, і тому перший визначений опорний план є неоптимальним. За алгоритмом симплекс-методу необхідно від нього перейти до іншого опорного плану задачі. 
Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х2» знаходимо відношення 
і вибираємо найменше значення. Згідно з даними симплексної таблиці бачимо, що min 
і тому з базису виключаємо змінну х5, а число а12= 3 називатимемо розв'язувальним елементом. Подальший перехід до нового опорного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана—Гаусса.
Друга симплексна таблиця має такий вигляд:
Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності 
для другого опорного плану. Цей план також неоптимальний, оскільки 
. Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:
|
|
|
В оцінковому рядку третьої симплексної таблиці немає від'ємних чисел, тобто всі 
і задовольняють умову оптимальності. Це означає, Що знайдено оптимальний план задачі:
2.Визначити, чи є оптимальними такі плани сформульованої задачі лінійного програмування:
min Z = 12x1 – 4x2 + 2x3;
а) Х = (8/7; 3/7; 0);
б) Х = (0; 1/5; 8/5);
в) Х = (1/3; 0; 1/3).
Розв’язання. Принцип розв’язування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розв’язок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій будуть однаковими за величиною, то припущення правильне. Протилежне можна висновувати в таких випадках:
1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.
2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі.
3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює значенню функції Z, тобто не виконується умова першої теореми двоїстості.
|
|
|
Запишемо двоїсту задачу до прямої задачі лінійного програмування:
max F = y1 + 2y2;
Перевіримо запропоновані плани на оптимальність.
1. Х = (8/7; 3/7; 0). Підставимо його в систему обмежень прямої задачі:
Обидва обмеження виконуються, і тому Х = (8/7; 3/7; 0) є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = 12 х 8/7 – 4 х 3/7 + 2 х 0 = 12.
Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x1 = 8/7 > 0; x2 = 3/7 > 0, то згідно з другою частиною другої теореми двоїстості можна записати перше та друге обмеження як рівняння і визначити у1 та у2:
Підставимо ці значення в третє обмеження системи двоїстої задачі:
;
.
Для визначених значень у1 = 4; у2 = 4 це обмеження не виконується, і тому відповідний план у = (4; 4) є недопустимим планом двоїстої задачі. Внаслідок цього наше допущення, що Х = (8/7; 3/7; 0) є оптимальним планом прямої задачі, виявилося помилковим.
2. Х = (0; 1/5; 8/5). Підставимо цей план у систему обмежень прямої задачі:
|
|
|
План допустимий, і для нього Z = 12 х 0 – 4 х 1/5 + 2 х 8/5 = 12/5.
Визначимо відповідний план двоїстої задачі. Оскільки компоненти x2 та x3 додатні, то друге і третє обмеження двоїстої задачі можна записати як рівняння:
Перевіримо, чи виконується перше обмеження двоїстої задачі для визначених значень у1 та у2: 2 х 8/5 + 2/5 = 18/5 < 12. Отже, перше обмеження виконується, і тому у = (8/5; 2/5) є допустимим планом двоїстої задачі. Для нього
F = 8/5 + 2 х 2/5 = 12/5 = Z.
З огляду на викладене можна висновувати, що Y* = (8/5; 2/5) є оптимальним планом двоїстої задачі, а X* = (0; 1/5; 8/5) — оптимальним планом прямої задачі.
Наше припущення відносно запропонованого плану виявилося правильним.
3. Х = (1/3; 0; 1/3). Для цього плану обмеження прямої задачі виконуються так:
Оскільки Х = (1/3; 0; 1/3) є недопустимим планом, то він не може бути також оптимальним планом прямої задачі.
Отже, перевірка запропонованих планів на оптимальність дала такі результати: а) ні; б) так, Х* = (0; 1/5; 8/5), min Z = 12/5; в) ні.
Дата добавления: 2018-04-05; просмотров: 208; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!