Теорема 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

У цій задачі умова балансу виконується, тому вводити фіктивні пункти немає потреби.