Тема 3 Задача лінійного програмування та мето ди її розв ’ язання

задача

розв’язання транспортної задачі

транспортної задачі.
4.3 Метод північно-західного кута(діагональний).
4.4 Метод найменших витрат.
4.5 Метод потенціалів.

Высшая школа, 1993. – 336 с.
2.Іванюта І.Д. Практикум з математичного

програмування: Навчальний посібник/ І.Д. Іванюта, В.І. Рибалка, І.А. Рудоміра – Дусятська. – К. : «Слово», 2008. – 296 с.
3.Кучма М.І. Математичне програмування: приклади і задачі: Навчальний посібник/ М.І. Кучма. - Львів: «Новий Світ - 2000», 2006. – 344 с.
4. А. Черемис, Р. Юринець, О. Мищишин. Методи оптимізації в економіці. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 152 с.

найпоширеніших задач лінійного програмування. Її мета – розробка найбільш раціональних

шляхів і способів транспортування однорідної продукції від постачальників до споживачів.

пунктах постачання А1,А2,…… Am (надалі постачальники) міститься однорідна продукція у

кількості відповідно а1, а2,….. аm. Цю продукцію потрібно перевезти в n пункти призначення B1,B2,…… Bn (надалі споживачі) у кількості відповідно b1, b2,….. bn. Вартість перевезення одиниці товару (тариф) із пункту Аi в пункт Bj дорівнює сji.

сji→ min

(4.1)
за умов
∑xji =ai (i=1,2…..m) (4.2)
∑xji =bj (j=1,2…..n) (4.3)
xji≥0 (i=1,2…..m; j=1,2…..n) (4.4)

можна використати для знаходження розв’язку деяких економічних задач, які не

мають нічого спільного з транспортуванням вантажів. У цьому разі величини тарифів перевезення сji мають різний зміст залежно від конкретної задачі. До таких задач належать наступні:

сji означають продуктивність праці.
Розміщення сільськогосподарських культур за ділянками землі різної

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

виконується умова балансу
∑bj = ∑ai

(4.5)
То задача називається закритою або збалансованою.

(i=1,2…..m; j=1,2…..n), який задовольняє умови обмеження (4.2) – (4.4).
Означення 4.3.

Опорний план транспортної задачі називається не виродженим, якщо він містить N=m+n-1 додатних елементів xji

елементів, то він називається виродженим.
Означення 4.5. Оптимальним планом транспортної задачі

називають матрицю Х* , яка задовольняє умови задачі (4.2) – (4.4) і для якої цільова функція F набуває мінімального значення

).
Транспортна задача має розв’язок тоді і тільки тоді, коли вона

збалансована, тобто виконується умова (4.5).

був оптимальним необхідно і достатньо, щоб йому відповідала така система

із m+n чисел ui (i=1,2…..m) vj ( j=1,2…..n) для якої виконуються умови
vj - ui = сji для xji>0
vj - ui ≤ сji для xji=0.
Означення 4.6. Числа vj та ui називаються потенціалами строк та стовпців.

заповнення верхньої клітинки таблиці x11 , в яку записують менше

з двох чисел a1 та b1.
Далі переходять до наступної клітинки в рядку або стовпчику і заповнюють ії і т.д. Закінчують заповнювати таблицю у правій нижній клітинці.

від величин ai та bj і зовсім не залежить від

вартостей перевезення сji, а тому він буде далекий від оптимального.

що на кожному кроці заповнюють клітинки таблиці, яка має найменшу

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

початкового плану транспортної задачі приступаємо до розрахунку потенціалів строк і

стовпців для заповнених кліток:
vj - ui = сji для xji>0 (4.6)

m+n невідомих містить m+n-1 рівнянь. Прийнявши одне невідоме за нуль,

наприклад, u1=0, решту знаходимо.

обчислюємо оцінки вільних клітинок:
Δji =vj - ui - сji
Якщо,

Δji ≤0, то побудований опорний план є оптимальним

m+n невідомих містить m+n-1 рівнянь. Прийнявши одне невідоме за нуль,

наприклад, u1=0, решту знаходимо.

клітинок:
Δji =vj - ui - сji
Якщо, Δji ≤0, то

побудований опорний план є оптимальним.

то опорний план не є оптимальним і треба від нього

переходити до нового опорного плану.

для якої порушені умови оптимальності. Якщо таких клітинок кілька, то

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

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

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

знак «+», а всім іншим по черзі- знаки «-»

та «+»;
У порожню клітинку переносять менше з чисел xji , що стоять у клітинках зі знаком «-». Одночасно це число додають до відповідних чисел, які розміщені в клітинках зі знаком «+».