sub> + х 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;
Такі завдання доцільно вирішувати за допомогою особливого варіанту симплекс-методу - так званого методу потенціалів .
Всі транспортні завдання мають оптимальне рішення . Якщо все значення a j і b i в умовах транспортної задачі цілочисельні, то змінні x ij у всіх базисних рішеннях (а так само і в будь-якому оптимальному базисному рішенні) мають цілочисельні значення. <В
1.1 Складання опорного плану
Рішення транспортної завдання починається з знаходження опорного плану. Для цього існують різні способи, розглянемо найпростіший, так званий спосіб північно-західного кута. Пояснити його найпростіше буде на конкретному прикладі:
Умови транспортної завдання задані транспортної таблицею.
а
b
20
5
10
10
5
15
5
6
3
5
9
15
6
4
7
3
5
20
2
5
3
1
8
Заповнюватимемо таблицю перевезеннями поступово починаючи з лівої верхньої комірки ("північно-західного кута "таблиці). Будемо міркувати при цьому наступним чином. Пункт а 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).
5
6
4
7
3
1
8
На цьому розподіл запасів закінчено; кожен пункт призначення отримав вантаж, відповідно до своєї заявки. Це виражається в тому, що сума перевезень у кожному рядку дорівнює відповідному запасу, а в стовпці - заявці. Таким чином, нами відразу ж складено план перевезень, задовольняє балансовим умов. Отримане рішення є опорним рішенням транспортної задачі. Складений нами план перевезень, не є оптимальним за вартістю, так як при його побудові ми зовсім не враховували вартість перевезень З ij .
1.2 Метод потенціалів
Нехай є транспортна таблиця, відповідна початкового рішенням, х il = для базисного рішення змінних, х il = 0 для вільних змінних (комірки, відповідні вільним змінним, залишаються порожніми). Далі, нам потрібно таблиця витрат із заданими p ij . p> Відшукання симплекс множників. Заповнимо таблицю витрат, ...
