:
Перетворену систему обмежень запишемо у векторній формі:
Оскільки серед векторів Р1-Р5 маються 3 одиничних вектора, для даної задачі можна безпосередньо записати опорний план.
Таким є план Х=(0; 0; 0; 20; 10; 36), який визначається системою тривимірних одиничних векторів Р3, Р4, Р5, які утворюють базис тривимірного векторного простору.
Складемо сімплексну таблицю для I ітерації (таб. 1), підрахувавши значення F0, zi - ci і перевіряємо вихідний план на оптимальність.
0=(c, P0); z1=(c, P1)=0; z2=(c, P2)=0; z3=(c, P3)=0; 4=(c, P4)=0; z5=(c, P5)=0; 1 - c1=0 - 7=- 7; z2 - c2=0 - 4=- 4.
Для векторів базису zi - ci=0.
Таблиця 1
iБазісЦ б Р 0 74000Р 1 Р 2 Р 3 Р 4 Р 5 1Р 3 020221002Р 4 010110103Р 5 036260014-7-4000
Таким чином, за 4 рядку таблиці 1 видно, що план не оптимальний, тому значення zi - ci - негативні.
Далі визначаємо вектор, що підлягає виключенню з базису. Для цього знаходимо Q 0min (bi/a i1) для a i1 gt; 0 і Q 0min (bi/a i2) для a i2 gt; 0.
Таким чином, Q 0min (bi/a i1)=min (20/2; 10/1; 36/2)=20/2, а Q 0min (bi/a i2)=min (20/2; 10/1; 36/6)=36/6.
Min (20/2; 36/6)=36/6.
Таким чином, ми знайшли дозволяє елемент, що знаходиться на перетині другого рядка і стовпця вектора Р 2.
Отже, вектор Р 4 підлягає виключенню з базису.
Стовпець вектора Р 2 і другий рядок є напрямними.
Далі, складаємо таблицю для ітерації II (таб. 2).
Спочатку заповнюємо рядок вектора знову введеного в базис. Елементи цього рядка таб. 3 виходять з відповідних елементів таб. 2 поділом на дозволяє елемент.
Потім, заповнюємо елементи стовпців для векторів, що входять в новий базис. У цих стовпцях на перетині рядків і стовпців однойменних векторів проставляємо одиниці, а всі інші елементи думаємо рівними нулю.
Для визначення інших елементів таб. 2 застосовуємо правило прямокутника.
Даний цикл продовжується до тих пір, поки всі значення zi - ci - не стануть позитивними.
Таким чином, в таб. 2 ми запишемо всі ітерації обчислювального процесу.
Таблиця 2
iБазісЦ б Р 0 74000Р 1 Р 2 Р 3 Р 4 Р 5 1Р 3 081,3010-0,32Р 4 040,6001-0,163Р 2 460,31000,16424-5,60000,61Р 1 76,15100,70-0,22Р 4 00,300-0,41-0,023Р 2 44,1501-0,200,2458,4004,30-0,71Р 1 710110,5002Р 4 00,71500,1-0,42103Р 5 020,7505-10147003,53,600
Отже, серед значень zi - ci немає негативних, отже, опорний план оптимальний і F max=70.
Двоїста задача
Пряма задача має вигляд:
х1, х2? 0
F=7х1 + 4х2
Хопта. =(7; 4).
Max F=57.
Складемо двоїсту модель і за допомогою теорем подвійності знайдемо оптимальне рішення двоїстої моделі:
Двоїста модель:
=20y1 + 10y2 + 36y3? min
Так як ми вже знайшли рішення вихідної задачі (таб. 2), отже, ми знайшли і рішення двоїстої задачі:
y1=3,6; y2=0; y3=0. (ітерація III в симплекс-таблице 2).
Таким чином оптимальне рішення двоїстої задачі=yопт (3,6; 0; 0).
Підставами компоненти оптимального рішення двоїстої задачі у функцію двоїстої моделі:
Z=20 * 3,6 + 10 * 0 + 36 * 0=70 + 0 + 0=70
Отже, Z=F=70.
Звіт за результатами:
Microsoft Excel 12.0 Звіт по результатамРабочій лист: [Стариков ЕММ - решеніе.xlsx] Завдання лінійного программірованОтчет створено: 01.10.2012 17: 06: 32Целевая комірка (Максимум) ЯчейкаІмяІсходное значеніеРезультат $ D $ 10оптімальние значення цільова функція7070Ізменяемие ячейкіЯчейкаІмяІсходное значеніеРезультат $ B $ 10оптімальние значення х1 * 1010 $ C $ 10оптімальние значення х2*00ОграниченияЯчейкаИмяЗначениеФормулаСтатусРазница$D$5коэф в 1 обмеженні ліва часть20 $ D $ 5 lt;=$ F $ 5связанное0 $ D $ 6коеф під 2 обмеженні ліва часть10 $ D $ 6 lt;=$ F $ 6связанное0 $ D $ 7коеф в 3 обмеженні ліва часть20 $ D $ 7 lt;=$ F $ 7не связан.16 $ B $ 10оптімальние значення х1 * 10 $ B $ 10 gt;=0не связан.10 $ C $ 10оптімальние значення х2 * 0 $ C $ 10 gt;=0связанное0
Звіт по межам:
Microsoft Excel 12.0 Звіт по пределамРабочій лист: [Стариков ЕММ - решеніе.xlsx] Звіт по межам 1Отчет створено: 01.10.2012 17: 08: 24ЦелевоеЯчейкаІмяЗначеніе $ D $ 10оптімальние значення цільова функция70ИзменяемоеНижнийЦелевойВерхнийЦелевойЯчейкаИмяЗначениепределрезультатпределрезультат$B$10оптимальные значення х1 * 10001070 $ C $ 10оптімальние значення х2 * 0070070
Звіт по стійкості:
