(10/1; 28/4; 24/1)=28/4.
Min (24/4; 28/4)=28/4.
Таким чином, ми знайшли дозволяє елемент, що знаходиться на перетині другого рядка і стовпця вектора Р 2.
Отже, вектор Р 4 підлягає виключенню з базису.
Стовпець вектора Р 2 і другий рядок є напрямними.
Далі, складаємо таблицю для ітерації II (таблиця 3).
Спочатку заповнюємо рядок вектора знову введеного в базис. Елементи цього рядка таблиці 3 виходять з відповідних елементів таблиці 2 поділом на дозволяє елемент.
Потім, заповнюємо елементи стовпців для векторів, що входять в новий базис. У цих стовпцях на перетині рядків і стовпців однойменних векторів проставляємо одиниці, а всі інші елементи думаємо рівними нулю. Для визначення інших елементів таблиці 3 застосовуємо правило прямокутника.
Даний цикл продовжується до тих пір, поки всі значення zi - ci - не стануть позитивними.
Таким чином, в таблиці 3 ми запишемо всі ітерації обчислювального процесу.
Таблиця 3
iБазісС б Р 0 48000Р 1 Р 2 Р 3 Р 4 Р 5 1Р 3 030,7501-0,2502Р 2 870,25100,2503Р 5 0172,7500-0,251456-200201Р 1 44101, 330,3302Р 2 8601-0,330,3303Р 5 0600-3,670,671564002,671,330
Отже, серед значень zi - ci немає негативних, отже, опорний план оптимальний і F max=64.
Пряма задача має вигляд:
х1, х2? 0
F=4х1 + 8х2
Хопта. =(4; 6).
Max F=64.
Складемо двоїсту модель і за допомогою теорем подвійності знайдемо оптимальне рішення двоїстої моделі:
Двоїста модель:
Z=10y 1 + 28y 2 + 24y 3? min
Так як ми вже знайшли рішення вихідної задачі (таблиця 3), отже, ми знайшли і рішення двоїстої задачі:
y1=2,67; y2=1,33; y3=0. (ітерація III в симплекс-таблице 3).
Таким чином оптимальне рішення двоїстої задачі=yопт (2,67; 1,33; 0).
Підставами компоненти оптимального рішення двоїстої задачі у функцію двоїстої моделі:
Z=10 * 2,67 + 28 * 1,33 + 24 * 0=26,7 + 37,3 + 0=64
Отже, Z=F=64.
Завдання 2
Запишемо і перетворимо матрицю коефіцієнтів системи.
??
Таким чином, ми отримали систему обмежень з одиничним базисом (х3, х4, х5):
Відкидаючи базисні змінні, отримаємо стандартну задачу ЛП:
Висловимо функцію мети через вільні невідомі х1 і х2. Маємо:
Тоді:
Таким чином,? min допоміжної задачі не дорівнює 0, отже, вихідна задача не володіє опорним рішенням (несовместна).
Завдання 3
Таблиця 4 Вихідні дані задачі
ПоставщікПотребітельЗапаси грузаВ1В2В3В4В5А11391531853А278610917А316410112930Потребность2020201327
Попит=20 + 20 + 20 + 13 + 27=100
Пропозиція=53 + 17 + 30=100
Таким чином, дана ТЗ - закрита.
Складемо початковий план за методом найменшої вартості (таблиця 5).
Таблиця 5
ПоставщікПотребітельЗапаси грузаВ1В2В3В4В5А120 1391513 320 1853А27817 610917А31620 43 10117 2930Потребность2020201327
n + m - 1=3 + 5-1=7 - не відповідає числу заповнених клітин
Загальні транспортні витрати дорівнюють:
Z 1=20 * 13 + 20 * 4 + 17 * 6 + 3 * 10 + 13 * 3 + 20 * 18 + 7 * 29=260 + 80 + 102 + 30 + 39 + 360 +203=1 074
Перевіримо складений план на оптимальність методом потенціалів.
Розрахуємо потенціали, виходячи з того, що потенціал рядки А1=0 (таблиця 6).
Таблиця 6
ПоставщікПотребітельЗапаси грузаВ1В2В3В4В5А120 1391513 320 1853U1=0А27817 610917U2=7А31620 43 10117 2930U3=11Потребность2020201327V1=13V2=- 7V3=- 1V4=3V5=18
Далі, розрахуємо тіньові ціни (таблиця 7 - тіньові ціни сірим кольором).
Таблиця 7
ПоставщікПотребітельЗапаси грузаВ1В2В3В4В5А120 1 316 916 1513 320 1853U1=0А2-13 78817 6 - 0 10-16 9 + 17U2=7А3-8 +1620 43 10 + - 3117 29 - 30U3=11Потребность2020201327V1=13V2=-7V3=- 1V4=3V5=18
Наявність тіньових цін означає не оптимальність наявного плану, отже, для поліпшення плану намічаємо маршрут з найменшою негативною тіньової ціною і для цього маршруту визначаємо цикл перерозподілу. Обсяг перевезеного вантажу чисельно дорівнює мінімальному значенню з тих обсягів вантажу, які вказані в клітинах зі знаком мінус. Таким чином, ? (А2, В5)=min (17; 7)=7.
Отже, складаємо новий план (таблиця 8).
Даний цикл триває до тих пір, поки всі тіньові цін...
