Теорема 2.

Якщо для всіх векторів P_j, виконується умова

Δ _j≥ 0, (j=1, 2, 3…..n) (для задачі на максимум)

або

Δ _j≤ 0, (j=1, 2, 3…..n) (для задачі на мінімум),

то опорний план Х^*=((х₁)^*, (х₂)^*,......... (х_n)^*) є оптимальним.

Якщо після побудови симплекс-таблиці виявилось, що виконуються умови Т.1 (пункт а)), або Т.2 розв’язання задачі припиняється. Якщо виконуються умови Т.1 (пункт б)), то потрібно перейти до нового оптимального опорного плану, побудувавши наступну симплексну таблицю. Для переходу до нового опорного плану треба один вектор вивести з базису і на його місце ввести новий вектор, який не належить базису. У базис вводять вектор, якому відповідає найбільша за абсолютною величиною від’ємна оцінка Δ _j. Нехай існує така оцінка в k- му стовпці, тобто max| Δ _j | = Δ _k.

Δ _j≤ 0

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

Q= min(b_i/a_ik) (i=1, 2…..m),

мінімальне значення якого досягається при i=r. Елемент a_rk називається розв’язувальним.

Рядок Р_r і стовпець Р_к на перетині яких знаходиться розв ’ язувальний елемент a_rk, називають розв’язувальним. Для перерахунку елементів нової (наступної) симплекс – таблиці користуються методом Жордана – Гауса.

3. Метод штучної бази.

Застосовується у тих випадках, коли в вихідній задачі ЛП, яка записана у канонічному вигляді, в системі обмежень немає необхідної кількості одиничних ортогональних незалежних векторів P_j, тобто важко вказати початковий опорний план.

М-метод полягає у використанні правил симплекс – методу до так званої задачі ЛП. Вона отримується із початкової додованням до лівої частини системи рівнянь таких штучних одиничних векторів з відповідними невід’ємними штучними змінними, щоб знову отримати m одиничних ортогональних лінійно незалежних векторів.

У цільовій функції задачі ЛП штучні змінні мають коефіцієнт - М (f(x)→ max) або +М (f(x)→ min), де під М ми розуміємо досить велике додатне число.

При розв’язанні цієї задачі симплекс-методом оцінки Δ _j будуть залежити від М. Для порівняння оцінок, треба пам’ятати, що М – достатньо велике додатне число, тому із базису будуть виключатися у першу чергу штучні вектори.

Якщо із базису всі штучні вектори вийшли, то ми отримали вихідну задачу.

Якщо оптимальний розв’язок М – задачі містить штучні змінні або М – задача нерозв’язна, то початкова задача також нерозв’язна.

Питання для самоконтролю.

1. В чому полягає симплекс-метод із стандартним базисом?

2. Коли використовують симплекс-метод зі штучним базисом?

3. Принципи заповнення симплекс-таблиці.

4. Що таке розв’язувальний елемент симплекс-таблиці?

5. Як перевірити опорний план на оптимальність?

6. Поясніть метод Жордана-Гауса.

7. Що таке штучні змінні?

Лекція 4

Тема лекції: Транспортна задача

Мета: ознайомити студентів з основними теоремами та методами розв’язання транспортної задачі

План лекції

1. Економічна та математична моделі транспортної задачі.

2. Основні теореми транспортної задачі.

3. Метод північно-західного кута (діагональний).

4. Метод найменших витрат.

5. Метод потенціалів.

Література:

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

2. Іванюта І.Д. Практикум з математичного програмування: Навчальний посібник/ І.Д. Іванюта, В.І. Рибалка, І.А. Рудоміра – Дусятська. – К.: «Слово», 2008. – 296 с.

3. Кучма М.І. Математичне програмування: приклади і задачі: Навчальний посібник/ М.І. Кучма. - Львів: «Новий Світ - 2000», 2006. – 344 с.

4. А. Черемис, Р. Юринець, О. Мищишин. Методи оптимізації в економіці. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 152 с.

1 Економічна та математична моделі транспортної задачі.

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

У загальному вигляді транспортну задачу можна сформулювати так: в m пунктах постачання А₁, А₂, …… A_m (надалі постачальники) міститься однорідна продукція у кількості відповідно а₁, а₂, ….. а_m. Цю продукцію потрібно перевезти в n пункти призначення B₁, B₂, …… B_n (надалі споживачі) у кількості відповідно b₁, b₂, ….. b_n. Вартість перевезення одиниці товару (тариф) із пункту А_i в пункт B_j дорівнює с_ji.

Математична модель транспортної задачі має такий вигляд:

F(x_ji)= ∑ ∑ x_ji с_ji→ min (1)

за умов

∑ x_ji =a_i (i=1, 2…..m) (2)

∑ x_ji =b_j (j=1, 2…..n) (3)

x_ji≥ 0 (i=1, 2…..m; j=1, 2…..n) (4)

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

· Оптимальне закріплення за верстатами операцій з обробки деталей. У них с_ji означає продуктивність праці.

· Розміщення сільськогосподарських культур за ділянками землі різної врожайності.

· Оптимальні призначення або проблема вибору.

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

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

2 Основні теореми транспортної задачі.

Означення 1. Якщо у транспортної задачі виконується умова балансу

∑ b_j = ∑ a_i (5)

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

Означення 2. Планом транспортної задачі називається сукупність величин x_ji (i=1, 2…..m; j=1, 2…..n), який задовольняє умови обмеження (2) – (4).

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

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

Означення 5. Оптимальним планом транспортної задачі називають матрицю Х^*, яка задовольняє умови задачі (2) – (4) і для якої цільова функція F набуває мінімального значення.

Теорема 1. (Необхідна і достатня умова існування розв’язку задачі ТЗ).

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

Теорема 2. Для того щоб деякий план Х транспортної задачі був оптимальним необхідно і достатньо, щоб йому відповідала така система із m+n чисел u_i (i=1, 2…..m) v_j (j=1, 2…..n) для якої виконуються умови

v_j - u_i = с_ji для x_ji> 0

v_j - u_i ≤ с_ji для x_ji=0.

Означення 6. Числа v_j та u_i називаються потенціалами строк та стовпців.

3. Метод північно-західного кута (діагональний.)

Побудова опорного плану задачі починають із заповнення верхньої клітинки таблиці x₁₁, в яку записують менше з двох чисел a₁ та b₁.

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

Зауважемо, що користуючись методом північно-західного кута початковий опорний план залежить від величин a_i та b_j і зовсім не залежить від вартостей перевезення с_ji, а тому він буде далекий від оптимального.

4. Метод найменшої вартості.

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

5. Метод потенціалів.

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

v_j - u_i = с_ji для x_ji> 0 (6)

Оскільки заповнених клітинок є m+n-1, то система рівнянь (6) із m+n невідомих містить m+n-1 рівнянь. Прийнявши одне невідоме за нуль, наприклад, u₁=0, решту знаходимо.

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

Δ _ji =v_j - u_i - с_ji

Якщо, Δ _ji ≤ 0, то побудований опрний план є оптимальним.

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

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

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

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

· Кожній вершині циклу приписують певний знак, причому вільній клітинці – знак «+», а всім іншим по черзі- знаки «-» та «+»;

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

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

Питання для самоконтролю.

1. Чому транспортну задачу вирішують іншими методами, якщо це задача лінійного програмування?

2. Яка транспортна задача називається закритою?

3. Що робити якщо транспортна задача відкрита?

4. Дайте означення опорного плану транспортної задачі.

5. Коли опорний план транспортної задачі не вироджений?

6. Що робити, якщо опорний план транспортної задачі вироджений?

7. Дайте означення оптимального опорного плану транспортної задачі.

8. Сформулюйте необхідні і достатні умови існування розв’язку транспортної задачі.

9. Як построїти потенціали строк і стовпців?

10. В чому полягає метод північно-західного кута?

11. В чому полягає метод найменших витрат?

12. Як визначити, що опорний план оптимальний?

13. Дайте означення циклу перерозподілу поставок.

Тема 4. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач.

Лекція 5.

Тема лекції: Двоїста задача лінійного програмування

Мета: ознайомити студентів з методами розв’язання двоїстих задач лінійного програмування, показати взаємозв’язок прямої та двоїстої задач.

План лекції

1. Математичні моделі двоїстих задач.

2. Основні теореми теорії двоістості.

3. Взаємозв’язок розв’язків прямої та двоїстої задач.

Література:

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

2. Іванюта І.Д. Практикум з математичного програмування: Навчальний посібник/ І.Д. Іванюта, В.І. Рибалка, І.А. Рудоміра – Дусятська. – К.: «Слово», 2008. – 296 с.

3. Кучма М.І. Математичне програмування: приклади і задачі: Навчальний посібник/ М.І. Кучма. - Львів: «Новий Світ - 2000», 2006. – 344 с.

4. А. Черемис, Р. Юринець, О. Мищишин. Методи оптимізації в економіці. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 152 с.

1 Математичні моделі двоїстих задач.

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

Початкова задача називається прямою задачею ЛП. Ці дві задачі тісно пов’язані між собою і утворюють єдину пару двоїстих задач.

Якщо пряма задача ЛП має вигляд:

Z=∑ c_ix_i → max (1)

за умов

∑ a_ijx_j ≤ b_i, (i=1, 2…..m) (2)

x_j ≥ 0 (j=1, 2…..n) (3)

то двоїста задача записується так:

F=∑ b_iy_i → min (1*)

за умов

∑ a_ijy_i≥ c_j, (j=1, 2…..n) (2*)

y_i≥ 0 (i=1, 2…..m) (3*)

В матричному вигляді їх можна представити таким чином: