/p>
Приклад 1.
Таблиця 4. Транспортна таблиця
20510105151520
Ми отримуємо наступну задачу:
х 11 + х 12 + х 13 + х 14 + х 15=15,
х 21 + х 22 + х 23 + х 24 + х 55=15,
х 31 + х 32 + х 33 + х 34 + х 35=20,
х 11 + х 21 + х 31=20,
х 12 + х 22 + х 32=5,
х 13 + х 23 + х 33=10,
х 14 + х 24 + х 34=10,
х 15 + х 25 + х 35=5;
х ij 0 для i=1,2,3; j=1,2,3,4,5;
До min=5х 11 + 6х 12 + 3х 13 + 5х 14 + 9х 15 + 6х 21 + 4х 22 + 7х 23 + 3х 24 + 5х 25 + 2х 31 + 5х 32 + 3х 33 + х 34 + 8х 35;
Такі завдання доцільно вирішувати за допомогою особливого варіанту симплекс-методу - так званого методу потенціалів.
Усі транспортні завдання мають оптимальне рішення. Якщо все значення aj і bi в умовах транспортної задачі цілочисельні, то змінні x ij у всіх базисних рішеннях (а так само і в будь-якому оптимальному базисному рішенні) мають цілочисельні значення [3].
. 4.2 Складання опорного плану
Рішення транспортної задачі починається з знаходження опорного плану. Для цього існують різні способи, розглянемо найпростіший, так званий спосіб північно-західного кута. Пояснити його найпростіше буде на конкретному прикладі:
Умови транспортної задачі задані транспортної таблицею.
Таблиця 5. Транспортна таблиця
а b20510105155635915647352025318
Заповнюватимемо таблицю перевезеннями поступово починаючи з лівої верхньої комірки ( північно-західного кута таблиці). Будемо міркувати при цьому наступним чином. Пункт а 1 подав заявку на 20 одиниць вантажу. Задовольнимо цю заявку за рахунок запасу 15, наявного в пункті b 1, і запишемо перевезення 15 в клітці (1,1). Після цього доповнимо заявку за рахунок заявка пункту b 2, і запишемо 5 в клітці (1,2), тепер заявка задоволена, але в пункті b 2 залишилося ще 10 одиниць вантажу. Задовольнимо за рахунок них заявку пунктів а 2 (5 одиниць клітина 2,2) і а 3 (5 одиниць клітина 2,3). На складі b 3 є запас в 20 одиниць, за рахунок його ми задовольнимо залишилися заявки а 3 (решта 5 одиниць клітина 3,3), а 3 (10 одиниць клітина 3,4) і а 5 (5 одиниць клітина 3,5).
Таблиця 6. Транспортна таблиця
5647318
На цьому розподіл запасів закінчено; кожен пункт призначення отримав вантаж, відповідно до своєї заявки. Це виражається в тому, що сума перевезень в кожному рядку дорівнює відповідному запасу, а в стовпці - заявці. Таким чином, нами відразу ж складено план перевезень, що задовольняє балансовим умов. Отримане рішення є опорним рішенням транспортної задачі. Складений нами план перевезень, не є оптимальним за вартістю, так як при його побудові ми зовсім не враховували вартість перевезень З ij [4].
1.4.3 Метод потенціалів
Нехай є транспортна таблиця, відповідна початкового рішенням, х il=для базисного рішення змінних, х il=0 для вільних змінних (осередки, відповідні вільним змінним, залишаються порожніми). Далі, нам потрібно таблиця витрат із заданими p ij.
Відшукання симплекс множників. Заповнимо таблицю витрат, залишивши осередки, відповідні вільним змінним, порожніми. У крайній правий стовпець внесемо значення невідомих u 1, ..., um, в нижній рядок - значення невідомих v 1, ..., vn,. Ці m + n невідомих для всіх (i, j), відповідних базисним змінним, повинні задовольняти лінійній системі рівнянь
u i + v j=p ij. (7)
Таблиця 7. Таблиця витрат
pllpljplnul..........pilpijpinui..........pmlpmjpmnumvl ... vj ... vn
Для всіх базисних рішень ця система має трикутний вигляд, ранг її матриці дорівнює n + m - 1. Отже, систему завжди можна вирішити наступним способом.
Вважають vn=0. Якщо значення k невідомих визначені, то в системі завжди є рівняння, одне з невідомих в якому вже знайдено, а інше ще немає.
Змінні ui і vj симплекс - множниками. Іноді вони називаються також потенціалами, а цей метод рішення називають методом потенціалів.
Приклад 2.
Таблиця 8. Транспортна таблиця
5u1647u2318u3v1v2v3v4v5
v 5=0 ® u 3=8, так як u 3 + u 5=p 35=8, ® v 4=- 7, оскільки u 3 + v 4=p 34=1 , ® v 3=- 5, так як u 3 + v 3=3, ® u 2=12 ® v 2=- 8, ® v 1=- 6 ® u 1=11.
Симплекс - мн...
