початку заповнюємо рядок вектора знову введеного в базис. Елементи цього рядка таб. 3 виходять з відповідних елементів таб. 2 поділом на дозволяє елемент.
Потім, заповнюємо елементи стовпців для векторів, що входять в новий базис. У цих стовпцях на перетині рядків і стовпців однойменних векторів проставляємо одиниці, а всі інші елементи думаємо рівними нулю.
Для визначення інших елементів таб. 3 застосовуємо правило прямокутника.
Даний цикл продовжується до тих пір, поки всі значення zi - ci - не стануть позитивними.
Таким чином, в таб. 3 ми запишемо всі ітерації обчислювального процесу.
Таблиця 3
iБазісС б Р 0 66000Р 1 Р 2 Р 3 Р 4 Р 5 1Р 3 0203,2010-0,42Р 4 030,6001-0,23Р 2 680,41000,2448-3,60001, 21Р 3 04001-5,30,62Р 1 651001,6-0,33Р 2 66010-0,60,356600060
Отже, серед значень zi - ci немає негативних, отже, опорний план оптимальний і F max=66.
4. Двоїста задача
Пряма задача має вигляд:
х1, х2? 0
F=6х1 + 6х2
Хопта. =(7; 6)
Max F=66
Складемо двоїсту модель і за допомогою теорем подвійності знайдемо оптимальне рішення двоїстої моделі:
Двоїста модель:
Z=36y1 + 11y2 + 40y3? min
Так як ми вже знайшли рішення вихідної задачі (таб. 3), отже, ми знайшли і рішення двоїстої задачі:
y1=0; y2=6; y3=0. (ітерація III в симплекс-таблице 3).
Таким чином оптимальне рішення двоїстої задачі=yопт (0; 6; 0).
Підставами компоненти оптимального рішення двоїстої задачі у функцію двоїстої моделі:
Z=36 * 0 + 11 * 6 + 40 * 0=0 + 66 + 0=66
Отже, Z=F=66.
5. Транспортна задача
На трьох складах А 1, А 2 і А 3 зберігається а 1=100, а 2=200, а 3=60 + 10n одиниць одного і того ж вантажу, відповідно. Цей вантаж потрібно доставити трьом споживачам В 1, В 2 і В 3, замовлення яких b 1=190, b 2=120, b 3=10m одиниць вантажу, відповідно. Вартості перевезень c ij одиниці вантажу з i-го складу j-му споживачеві вказані у відповідних клітинах транспортної таблиці:
Таблиця 4
Потреби запасів 1 У 2 У 3 b 1=190b 2=120b 3=400А 1 а 1=100424А 2 а 2=200453А 3 а 3=100156
. Порівнюючи сумарний запас і сумарну потребу у вантажі, встановити, чи є модель транспортної задачі відкритою або закритою. Якщо модель відкрита, то її необхідно закрити, додавши фіктивний склад А 4 із запасом а 4=b-а у випадку а lt; b або фіктивного споживача В 4 з потребою b 4=ab у випадку а gt; b і поклавши відповідні їм тарифи перевезень нульовими.
. Скласти початковий план перевезень методом північно-західного кута і методом найменшої вартості.
. Методом потенціалів перевірити початковий план перевезень на оптимальність в сенсі сумарної вартості перевезень, і якщо це не так, то скласти оптимальний план
,
забезпечує мінімальну вартість перевезень. Знайти цю вартість.
. Вирішити завдання в MS Excel в режимі «пошук рішення» . Відповіді, отримані в результаті рішень «вручну» і за допомогою Excel, повинні збігатися.
Рішення:
Потреба=190 + 120 + 400=710
Можливості=100 + 200 + 100=400
Таким чином, дана транспортна задача (ТЗ) - відкрита.
Отже для вирішення такого завдання необхідно ввести фіктивного постачальника - А4, що має запаси вантажу рівні 310 одиниць, тим самим ми збалансували попит та пропозиція (таблиця 5).
Таблиця 5
ПоставщікПотребітельЗапаси грузаВ1В2В3А1424100А2453200А3156100А4000310Потребность190120400710
Таблиця 6
ПоставщікПотребітельЗапаси грузаВ1В2В3А1 100 424100А2 90 4 110 53200А31 10 5 90 6100А400 310 0310Потребность190120400710
n + m - 1=4 + 3-1=6 - відповідає числу заповнених клітин
Загальні транспортні витрати дорівнюють:
Z 1=100 * 4 + 90 * 4 + 110 * 5 + 10 * 5 + 90 * 6 + 310 * 0=400 + 360 + 550 + 50 + 540 + 0=1900
Перевіримо складений план на оптимальність методом потенціалів.
Розрахуємо потенціали, виходячи з того, що потенціал рядки А1=0 (таблиця 7).
Таблиця 7
ПоставщікПотребітельЗапаси грузаВ1В2В3А1 100 424100U1=0А2 90 4 110 53200U...
