Економічна інтерпретація прямої та двоїстої задачі.

Оптимальне значення Ц.Ф. даної задачі ЛП можна розглядати як Z_опт = ƒ(b₁, b₂,.., b_m)

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

, i = 1..m

Транспортна задача лінійного програмування

(в найпростішому варіанті – класична).

Нехай існує m продуктів виробництва продукції i = 1..m і n пунктів споживання j =1..n.

Відомо об’єми виробництва a₁, a₂,.., a_m та об’єми споживання b₁,b₂,.., b_n. Будемо рахувати, що загальний валовий об’єм виробництва співпадає з загальним об’ємом продукції:

Відома вартість перевезення одиниці продукції від кожного пункту виробництва до кожного пункту споживання, тобто відома матриця транспортних витрат:

Де c_ij - вартість перевезення одиниці продукції із i-го пункту виробництва в j -тий пункт споживання.

Встановити таким чином об’єм перевезення по кожному маршруту i→j, що сумарні витрати на виробництво мінімальні, а попит всіх постачальників задоволений.

Введемо шукані об’єми перевезень від i-го постачальника до j-того споживача x_ij.

Всього невідомих m x n.

 

c₁₁x₁₁ + c₁₂x₁₂ + … + c_1nx_1n + c₂₁x₂₁ + …+ c_2nx_2n + … + c_mnx_mn

x₁₁ + x₁₂ + … + x_1n = a₁

x₂₁ + x₂₂ + … + x_2n = a₂

_{…………………………………..}

x_m1 + x_m2 + … + x_mn = a_m

 

x₁₁ + x₂₁ + … + x_m1 = b₁

x₁₂ + x₂₂ + … + x_m2 = b₂

_{……………………………………}

x_1n + x_2n + … + x_mn = b_n

Матрицю Х називають планом перевезень Т- задачі. А змінні x_ij -перевезення.

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

В практиці існує як задача де виконується рівність між сумарними ресурсами і сумарним споживанням (умова балансу 3.5).

так і задача де виконується нерівність 3.6.

Задача 3.1 – 3.4 при умові 3.5 називається закритою моделлю, а при умові 3.6 – відкритою моделлю.

Рівність 3.5 є необхідною і достатньою умовою сумісності систем рівнянь 3.2 і 3.3.

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

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

 

Властивості транспортної задачі.

1. Транспортна завжди допустима і має оптимальний розв’язок. Нехай x_ij=а_іb_j/D, де D =∑ а_і =∑b_j. Доведемо, що такий набір розв’язків – допустимий розв’язок Т–задачі.

Підставимо ці числа в будь-яке із М обмежень. Тоді маємо:

Доведемо обмеження допустимих множин. За умовою задачі x_ij ≤ min (a_i). Так як кожна координата допустимого вектора обмежена, то і весь вектор буде обмеженим, тобто вся множина обмежена. На допустимій множині функція обмежена, а з цього слідує, що існує оптимальний розв’язок.

2. Ранг матриці Т-задачі r(A)= m+n-1. Якщо в Т-задачі всі цілі a_i і b_j, то хоча б один оптимальний розв’язок Т-задачі є цілочисленим.

 

Знаходження первинного опорного розв’язку Т-задачі.

Метод північно-західного кута.

Домовимося задавати Т-задачу наступною таблицею:

С11	…	С1n-1	C1n	a1
…	….	…	…	…
Cm1	…	Cmn-1	Cmn	am
b1	…	bn-1	bn	D

b₁... b_n - об’єми споживання; a₁… a_m - об’єми виробництва.

Якщо b₁ < a₁, то перший споживач повністю задоволений та у першого виробника залишається b₁- a₁ одиниць продукції. Якщо b₁ > a₁, то навпаки. Якщо b₁ = a₁, то перший споживач і перший виробник випадають. Таким чином, після заповнення північно-західної клітини випадає або один постачальник, або один споживач, або і той і інший. Закреслюємо відповідний стовпчик чи строку і корегуємо те, що залишилося. Частину таблиці, що залишилася можна вважати самостійною Т-задачею. В ній за тим самим правилом заповнюємо північно-західну клітку і т.д.

Початкове число строк та стовпчиків m+n. За методом північно-західної клітини заповнюється m+n-1 клітка. Деякі клітини можуть бути заповнені нулями. Доведено, що отриманий допустимий розв’язок є опорним, причому вектори, що відповідають заповненим клітинам і складають його базис.

Схема заповнення таблиці методом північно-західного кута.

А₁₁

 

А₁₂ А₂₁

 

А₁₃ А₂₂ А₃₁

 

 

Метод мінімального елементу в рядках.

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