Вихідні дані до транспортної задачі

Пряма задача лінійного програмування у цьому випадку записується у вигляді:

min F = 10х₁₁ + 15х₁₂ + 25х₁₃ + 20х₂₁ + 30х₂₂ + 30х₂₃

при обмеженнях:

х₁₁ + х₁₂ + х₁₃ = 40;

х₂₁ + х₂₂ + х₂₃ = 60;

х₁₁ + х₂₁ = 50;

х₁₂ + х₂₂ = 20;

х₁₃ + х₂₃ = 30;

х_іj ≥ 0; і = 1, 2; j = 1, 2, 3.

В системі обмежень будь – яке рівняння є лінійною комбінацією решти рівнянь. Тому з системи можна виключити одне рівняння, наприклад, друге. З решти рівнянь отримуємо нову систему:

х₁₃ = 40 - х₁₁ - х₁₂; (1)

х₂₁ = 50 – х₁₁; (2)

х₂₂ = 20 – х₁₂; (3)

х₂₃ = 30 – х₁₃ = - 10 + х₁₁ + х₁₂; (4)

Переконатися в правильності виключення другого рівняння попередньої системи можна наступним чином. Підставимо в нього вирази для х₂₁, х₂₂, х₂₃ з останньої системи рівнянь. Тоді отримуємо:

50 – х₁₁ + 20 – х₁₂ + 30 – х₁₃ = 60;

х₁₁ + х₁₂ + х₁₃ = 40.

Тобто, друге рівняння вироджується в перше у вихідній системі обмежень.

Підставляємо знайдені вирази для х₁₃ , х₂₁ , х₂₂ , х₂₃ в цільову функцію:

min F = 10х₁₁ + 15х₁₂ + 25(40 - х₁₁ - х₁₂) + 20(50 – х₁₁)+ 30(20 – х₁₂) +

30(- 10 + х₁₁ + х₁₂);

min F = - 5х₁₁ - 10х₁₂ + 2300 .

Зважаючи на те , що стала величина не впливає на пошук координат оптимуму, цільову функцію можна записати :

min F = - х₁₁ - 2х₁₂ .

За властивістю двоїстості рішення прямої задачі співпадає з рішенням двоїстої задачі:

mах F = х₁₁ + 2х₁₂ .

Оскільки х₁₃ ≥ 0, то отримуємо:

• з рівняння (1) 0 ≤ 40 – х₁₁ – х₁₂;

• з рівняння (2) 0 ≤ 50 – х₁₁;

• з рівняння (3) 0 ≤ 20 – х₁₂;

• з рівняння (4) 0 ≤ - 10 + х₁₁ +х₁₂.

Представимо цю систему у вигляді:

х₁₁ + х₁₂ ≤ 40;

0 ≤ х₁₁ ≤ 50;

0 ≤ х₁₂ ≤ 20;

х₁₁ +х₁₂ ≥ 10.

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

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

На вершині а: х₁₁=0; х₁₂=10; F=x₁₁+2x₁₂=0+2*10=20.

В точці в: х₁₁=0; х₁₂=20; F=0+2*20=40.

В точці с: х₁₁=20; х₁₂=20; F=20+2*20=60.

В точці d: x₁₁=40; х₁₂=0; F=40+2*0=40.

В точці е: х₁₁=10; х₁₂=0; F=10+2*0=10.

Таким чином, оптимальна точка с має координати: х₁₁^*=20; х^*₁₂=20; х₁₃^*=40 - х^*₁₁ - х₁₂^*= 40 – 20 – 20 = 0; х^*₂₁= 50 - х₁₁*= 50 – 20 = 30;

х₂₂^*= 20 - х^*₁₂= 20 – 20 = 0; х₂₃^*= - 10 + х^*₁₁+ х₁₂^*= - 10 + 20 + 20 = 30.

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

Ще однією класичною задачею лінійного програмування є задача щодо складу сировини (матеріалів, енергоносіїв тощо) для отримання продукції, щодо компонентів конструкції і т. д. В первинному вигляді вона виникла як задача про раціон.

При організації харчування великих колективів людей, наприклад, у війську, в лікарнях і т. д. , виникає потреба в складанні найбільш економічного раціону харчування, який задовольняє певним медичним вимогам. Для цього в наявності є n продуктів харчування (хліб, м’ясо, молоко, картопля і т. д. ), в яких утримується m корисних речовин (жирів, білків, вуглеводів, вітамінів і т. д.). Відомі наступні параметри:

• а_ij – вміст і – тої речовини в одиниці j – того продукту; а_ij ≥ 0;

і = 1,2,…, m;

• в_і – мінімальна кількість і – тої речовини, яка потрібна людині для

споживання у визначений період часу; в_і > 0;

• с_j – вартість одиниці j – того продукту; с_j> 0.

Якщо позначити кількість j – того продукту, що споживається, через х_j , то задача формалізується наступним чином:

min F =

при обмеженнях:

; х_j ≥ 0.

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

Приклад. Треба сконструювати самий дешевий кузов з використанням листового металу, скла та пластмаси. Загальна поверхня кузова (разом з дверцятами та вікнами) складає 14м², з них не менш, ніж 4 м², і не більше 5м² треба відвести під скло. Маса кузова не повинна перевищувати 150 кг. Скільки металу, скла та пластмаси треба використовувати? Характеристика матеріалів наведена в табл. 3.4.

Таблиця 3.4