Теорема 3
Якщо всі і
у транспортній задачі — цілі, то всі
у будь-якому ДБР (включаючи й оптимальний) також будуть цілими числами.
Метод потенцiалiв
Метод потенціалів – один з тих, що найчастіше використовують для розв’язання ТЗЛП. Цей метод є реалізацією симплекс-методу в умовах транспортної задачі.
Загальна схема алгоритму
Крок 1. Знайти початковий допустимий розв’язок.
Крок 2. Виділити з числа небазисних змінних ту, що вводиться до базису. Якщо всі небазисні змінні задовольняють умову оптимальності (симплекс-методу), закінчити обчислення; інакше – перейти до кроку 3.
Крок 3. Вибрати змінну, що виводиться з базису (використовуючи умову допустимості) із числа змінних поточного базису; потім знайти новий базисний розв’язок. Повернутися до кроку 2.
Далі ТЗЛП наводимо таблицею (табл. 5.1):
Таблиця 5.1
![]() | ![]() | … | ![]() | |||||
x11 | x12 | … | x1n | ![]() | ||||
![]() | ![]() | … | ![]() | |||||
x21 | x22 | … | x2n | ![]() | ||||
… | … | … | … | |||||
![]() | ![]() | … | ![]() | |||||
xm1 | xm2 | … | xmn | ![]() | ||||
![]() | ![]() | … | ![]() | ![]() |
Кількість рядків табл. 5.1 дорівнює кількості виробників m, а кількість стовпчиків – кількості споживачів n. Кожна клітина цієї таблиці відповідає деякій парі “виробник i – споживач j”. Кожному маршруту i, j відповідають вартість перевезення одиниці продукції та обсяг перевезення (кількість продукції)
. Вартість перевезень одиниці продукції
подано в правих верхніх кутах відповідних клітин. Обсяги виробництва та попиту виражено в кількостях виробів.
Реалізацію алгоритму розглянемо на прикладі задачі, наведеної в табл. 5.2.
Таблиця 5.2
У цій задачі умова балансу виконується, тому вводити фіктивні пункти немає потреби.