Лекція 4 транспортні задачі лінійного програмування (тзлп)

1. Математична модель тзлп

Приклад:

Постачальник		Споживач
Позначення	Запас вантажу	В1		В2		В3		В4
А1	а1=35	х11	5	х12	13	х13	6	х14	11
А2	а2=45	х21	4	х22	7	х23	12	х24	8
А3	а3=50	х31	9	х32	2	х33	3	х34	10
Потреба у вантажі		b1=30		b2=10		b3=65		b4=25

Запаси вантажу у 3 пунктах: а₁, а₂, а₃. Необхідно відправити 4 заявникам В₁, В₂, В₃, В₄.

Причому : а₁+а₂+а₃=b₁+b₂+b₃+b₄=130

Відома вартість перевезення вантажу.

Необхідно:

• визначити, скільки вантажу має отримати кожен споживач В_i від кожного виробника A_j;

• необхідно виконати заявки всіх споживачів В_і;

• вивести вантаж від усіх виробників А_j;

• забезпечити якнайменші (min) витрати на перевезення вантажу.

Позначимо: х_і­ – кількість одиниць вантажу при перевезенні від виробника А_і до споживача B_j. Це шукані змінні.

Запишемо умову виконання заявки споживачів В_і:

B₁: х₁₂+х₂₂+х₃₂=10

B₂: х₁₃+х₂₃+х₃₃=65

B₃: х₁₄+х₂₄+х₃₄=25.

Запишемо обмеження: (вивести весь вантаж)

:

:

:

Для отримання цільової функції необхідно додати витрати на переве­зення по всіх маршрутах:

, і=1, 2, 3; j=1, 2, 3, 4.

Математична модель транспортної задачі. Метод найменшого елемента.

; min вартість .

Найменша вартість (3,3) записуємо 40 (50-10)

Переходимо далі

Загальний вигляд

Маємо: m – постачальників;

n – споживачів

Постачальники		Споживачі
Позна­чення	Запас вантажу	В1	В2	…	Вj	…	Вn
А1	а1	c11	c21	…	c2ij	…	c1n
А2	а2	c21	c22	…	c2j	…	c2n
...	…	…	…	…	…	…	…
Аі	аi	ci1	ci2	…	cij	…	cin
...	…	…	…	…	…	…	…
Аm	am	cm1	cm2	…	cmj	…	cmn
Потреба у вантажі		b1	b2	…	bj	…	bn

Умова задовільнення заявки кожного споживача B_j

. (*)

Умова вивезення вантажу від кожного A_j

. (**)

(***)

, , . (****)

Відкрита модель ТЗ

У випадку, коли сумарний запас вантажу рівний сумарній потребі у ньому, тобто , модель ТЗ є закритою (ЗТЗ). Коли ж , модель ТЗ є відкритою (ВТЗ).

Розглянемо варіанти ВТЗ.

1) не обов’язкова вимога, щоб весь запас вантажу повинен бути вивезений (запаси більші за потребу)

.

Умова на вивезення вантажу: замість (**) отримаємо

, .

Умова на потреби споживачів (*), мета (***) та умова на невід’ємні значення (****) залишаються як в ЗТЗ.

2) загальна потреба перевищує сумарний запас (запаси менші за потребу)

,

тоді умова на вивезення (**), мета (***) та умова на невід’ємні значення (****) залишаються як в ЗТЗ.

Зазначимо, що ВТЗ зводяться до ЗТЗ.

Для 1-го варіанту: вводимо m+1 фіктивний виробник A_m+1 з запасом вантажу , а . Отримуємо ЗТЗ.

Для 2-го варіанту: вводимо фіктивний n+1 споживач B_n+1, зокрема з потребою , а . Отже, отримуємо ЗТЗ.