Двоїсті задачі

Будь-якій задачі лінійного програмування, яку називають вихідною або прямою, можна поставити у відповідність іншу задачу, яку називають двоїстою або сполученою.

В теорії двоїстості використовуються чотири пари двоїстих задач. Наведемо дві із них, використовуючи матричну форму запису.

Вихідна задача Двоїста задача

1.

2.

Якщо в двоїстих задачах одна із них має розв’язок, то існує розв’язок і для другої задачі і їх оптимальні значення співпадають, тобто

.

Приклад. Побудувати двоїсту задачу до ЗЛП

Розв’язання. Помножимо першу нерівність на і одержимо таку систему обмежень

Відповідні матриці мають такий вигляд:

Транспонована матриця до матриці А має вигляд:

Двоїста задача до даної буде такою:

або

Транспортна задача

Транспортна задача широко використовується у плануванні. Це задача про знаходження найменших затрат плану перевезень однорідного продукту від постачальників до споживачів. Таку задачу називають транспортною задачею за критерієм вартості.

Будемо вважати, що в даних т пунктах-відправниках є відповідно одиниць деякого однорідного вантажу, який необхідно перевезти в п пунктів призначення відповідно по одиниць вантажу при умові, що

(4)

а вартість перевезення вантажу з і-го пункту відправлення в -й пункт призначення дорівнює . Треба скласти такий план перевезень, за яким їхня загальна вартість буде найменшою. Позначимо через кількість одиниць вантажу, що відправляється з і-го пункту в -й. Тоді функцією цілі буде сумарна вартість перевезень з усіх пунктів відправлення в усі пункти призначення, тобто

(5)

при умовах: вся продукція буде вивезена

;

і потреби всіх споживачів будуть задоволені:

а також

Приклад. Розв’язати транспортну ЗЛП за такими даними:

					Запаси
	3	5	7	11	50
	1	4	6	3	30
	5	8	12	4	40
потреби	40	35	25	20	120

Розв’язання. Умова (4) для даної задачі виконується, тобто сума запасів і сума потреб співпадають, то задача є закритою, або задачею з правильним балансом.

Розв’язання транспортної задачі слід починати з побудови вихідного опорного плану перевезень. Існує декілька методів побудови вихідного опорного плану. Розглянемо найпростіший метод північно-західного кута, який пропонує розпочинати заповнення таблиці з лівої верхньої клітини і так розмістити запаси по клітинах, щоб баланс не був порушений, а заповнених клітин всього було тобто 4 + 3 – 1 = 6. При цій умові план буде невиродженим. Одержимо таблицю 4.

Знайдемо

Для перевірки оптимальності одержаного плану і мінімальності цільової функції використаємо метод потенціалів. Якщо позначити через потенціали постачальників, а через потенціали споживачів, то опорний план буде

Таблиця 4.

					Запаси
	3 40 –	5 10 +	7	11	50	0
	1 +	4 25 –	6 5	3	30	–1
	5	8	12 20	4 20	40	5
потреби	40	35	25	20	120
	3	5	7	–1

оптимальним при умовах, що система із т + п чисел задовольняє умовам при при

Складемо систему вигляду для заповнених клітин і визначимо відповідні потенціали і при довільному значенні одного із них. Одержимо

Значення одержаних потенціалів запишемо у таблицю і перевіримо умови оптимальності для незаповнених клітин. При оптимальному плані виконуються такі умови

(6)

Одержимо:

Не для всіх оцінок умова (6) виконалась. Деякі оцінки мають додатні значення, а це вказує на те, що план не оптимальний і його можна покращити перерозподілом вантажу. Вантаж можна перезавантажити у ту порожню клітину, для якої оцінки додатні, тобто Перерозподіл вантажу здійснюється по циклу. Виберемо незаповнену клітину і там поставимо знак „+”, а потім рухаємося у заповнену клітину під прямим кутом (вгору чи в право) і там ставимо знак „–”, а потім у наступну заповнену клітину і там ставимо знак „+” і знову у заповнену клітину і там ставимо знак „–”. Цикл завершується у початковій незаповненій клітині, де вже є знак плюс. До циклу належить не більше двох клітин із одного рядка чи стовпця. Із тих завантажених клітин, у яких є знак „–” вантаж перевозиться у ті клітини, у яких є знак „+”. Для перевезення вибирають найменший вантаж, тобто

Після перерозподілу вантажу одержимо нову таблицю.

					Запаси
	3 15	5 35	7	11	50	0
	1 25 –	4	6 5 +	3	30	–2
	5 +	8	12 20 –	4 20	40	4
потреби	40	35	25	20	120
	3	5	8	0

Обчислимо

Для перевірки оптимальності одержаного плану знову складемо систему для заповнених клітин і визначимо потенціали і :

Перевіримо виконання умов (6) для незаповнених клітин. Одержимо:

Серед оцінок є додатні значення , то і цей план неоптимальний і його можна покращити. Вибираємо незаповнену клітину і йдемо по циклу і виставляючи знаки „+” та „–” відповідно. Найменшим буде вантаж Після перерозподілу вантажу одержимо таку таблицю.

					Запаси
	3 15 –	5 35	7 +	11	50	0
	1 5 +	4	6 25 –	3	30	–2
	5 20	8	12	4 20	40	2
потреби	40	35	25	20	120
	3	5	8	2

Обчислимо

Перевіримо оптимальність одержаного плану.

Для цього складемо систему для заповнених клітин:

Для незаповнених клітин перевіримо умову (6).

Серед оцінок є додатні: План можна покращити. Перезавантаження почнемо із незаповненої клітини із знаком „+” і підемо по циклу , виставляючи послідовно знаки „–” і „+”. Найменшим буде вантаж Перерозподіляємо вантаж і одержимо такий план (таблиця 5).

Обчислимо

Таблиця 5

					Запаси
	3	5 35	7 15	11	50	0
	1 20	4	6 10	3	30	–1
	5 20	8	12	4 20	40	3
потреби	40	35	25	20	120
	2	5	7	1

Перевіримо оптимальність цього плану за допомогою системи рівнянь для заповнених клітин:

Для незаповнених клітин перевіримо умову (6).

Умови оптимальності виконуються. Тоді цей план є оптимальним і

Відповідь: а або

На практиці часто буває так, що умова балансу (4) порушується. Такі моделі транспортних задач називаються відкритими. Можливі два випадки:

1. пропозиція постачальників перевищує попит споживачів, тобто виконується нерівність

; (7)

2. попит споживачів перевищує пропозицію постачальників, тобто виконується нерівність

. (8)

Для відкритих моделей також ставиться задача мінімізації цільової функції (5). Проте при виконанні умови (7) деяка частина вантажу залишається у постачальників, а при виконанні умови (8) споживачі недоотримають певну частину вантажу.

Відкриті моделі транспортної задачі зводяться до закритих. А саме, у першому випадку до розгляду вводиться фіктивний пункт споживання , потребу якого у вантажі приймають рівною величині

.

При цьому вартості перевезень одиниці вантажу з усіх пунктів постачання до пункту приймають рівними нулеві:

.

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

.

І, аналогічно попередньому випадку, вартості перевезень одиниці вантажу з пункту до всіх пунктів споживання приймають рівними нулеві:

.

Розглянемо наступний

Приклад. Розв’язати транспортну задачу за такими даними:

	В1	В2	В3	В4	Запаси
А1	2	3	1	4	40
А2	5	4	3	2	60
А3	1	6	2	3	15
Потреби	20	30	40	60

Оскільки потреби (20+30+40+60=150) перевищують запаси (40+60+15=115) на 35 одиниць, то вводимо фіктивного постачальника з запасом, рівним 30 одиницям. Маємо наступну таблицю, що відповідає закритій моделі задачі:

	В1	В2	В3	В4	Запаси
А1	2	3	1	4	40
А2	5	4	3	2	60
А3	1	6	2	3	15
А4	0	0	0	0	35
Потреби	20	30	40	60	150

Процес розвязання цієї задачі відображено в наступних таблицях.

	В1	В2	В3	В4	Запаси
А1	2 20 -	3 20 -	1	4	40	0
А2	5	4 10 -	3 40	2 10 +	60	1
А3	1 +	6	2	3 15 -	15	2
А4	0	0	0	0 35	35	-1
Потреби	20	30	40	60	150
	2	3	2	1

	В1	В2	В3	В4	Запаси
А1	2 10 -	3 30	1 +	4	40	0
А2	5	4	3 40 -	2 20 +	60	-2
А3	1 10 +	6	2	3 5 -	15	-1
А4	0	0	0	0 35	35	-4
Потреби	20	30	40	60	150
	2	3	5	4

	В1	В2	В3	В4	Запаси
А1	2 5	3 30 -	1 5 +	4	40	0
А2	5	4	3 35 -	2 25 +	60	2
А3	1 15	6	2	3	15	-1
А4	0	0 +	0	0 35 -	35	0
Потреби	20	30	40	60	150
	2	3	1	0

	В1	В2	В3	В4	Запаси
А1	2 5 -	3	1 35 +	4	40	0
А2	5	4	3 5 -	2 55 +	60	2
А3	1 15	6	2	3	15	-1
А4	0 +	0 30	0	0 5 -	35	0
Потреби	20	30	40	60	150
	2	0	1	0

Таблиця 6.

	В1	В2	В3	В4	Запаси
А1	2	3	1 40	4	40	0
А2	5	4 0	3 0	2 60	60	2
А3	1 15	6	2	3	15	-1
А4	0 5	0 30	0	0	35	-2
Потреби	20	30	40	60	150
	2	2	1	0

З останньої таблиці 6 визначаємо оптимальний план перевезень вихідної задачі:

.

Вартість перевезень за цим планом

.

Зауваження 1. З таблиці 6 випливає, що в пункт потрібно довезти 5, а в пункт - 30 одиниць вантажу “ззовні” (постачальникам А₁, А₂, А₃ нераціонально постачати вантаж до пункту взагалі).

Зауваження 2. Для перевірки плану на оптимальність методом потенціалів необхідно, щоб кількість завантажених клітинок була на одиницю менше, ніж кількість споживачів і постачальників разом взятих. Тому в таблиці 6 введено дві умовно завантажені клітинки та (в них поставлено нулі).

10