Лабораторна робота № 3 Симплекс-метод розв’язування задачі лінійного програмування Хід роботи.

Алгоритм симплекс - методу вирішення ЗЛП.

I. Побудова початкового опорного плану:

1) приведення задачі до канонічного виду;

2) приведення системи обмежень до кращого виду;

3) побудова першої симплексної таблиці;

4) перевірка умови оптимальності.

II. Перехід до негіршого опорного плану:

1) вибір вирішуючого стовпця;

2) вибір вирішуючого рядка;

3) вибір вирішуючого елемента;

3) симплексні перетворення й побудова 2-й симплексної таблиці;

4) перевірка умов оптимальності й або перехід до П, або кінець.

З а д а ч а.

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

F(x) = 40x₁+50x₂+100x₃+80x₄  max .

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

2,5x₁+2,5x₂+2x₃+1,5x₄ 100 (на трудові ресурси);

4x₁+10x₂+4x₃+6x₄ 260 (на напівфабрикати);

8x₁+7x₂+4x₃+10x₄ 370 (на верстатне устаткування);

x_j 0, j = 1,4

1) Перейдемо до канонічного виду:

F (x) = - 40х1-50х2-100х3-80х4  max

2) Додамо до лівих частин обмежень додаткові невід’ємні змінні:

2,5x₁+2,5x₂+2,5x₃+1,5x₄+x₅ = 100.

4x₁+10x₂+4x₃+6x₄+ x₆ = 260.

8x₁+7x₂+4x₃+10x₄+ x₇ = 370.

Тепер система обмежень має кращий вигляд.

3) Будуємо симплексну таблицю 3.1

Таблиця 3.1

С_б- стовпець коефіцієнтів базисних у ц.ф.

Б_п- базисні змінні; змінні, вхідні в кращі обмеження;

В - стовпець вільних членів у системі обмежень, представлених у кращому вигляді.

На перетині стовпців і рядків розташована матриця коефіцієнтів системи обмежень.

Рядок "функція цілі"-Z є індексним рядком, у якому розташовані коефіцієнти й j, j = 1, n, які розраховуються за формулами:

_j =СбВ = 0*100+0*260+0*370

₀ =Сб*Аj - Cj;

₁ = (2,5*0+4*0+8*0)+40 = 40 і т.д.

3) Початковий опорний план задачі:

х₀ = (0,0,0,0,100,260,370), Z(х₀).

Всі оцінки вільних змінних _j 0, j = 1;7 – план не оптимальний.

Виберемо найбільшу оцінку.

1) ₃=100, стовпець, якому належить ця оцінка, називається вирішуючим.

2) Елементи стовпця В ділимо на відповідні їм елементи вирішуючого стовпця.

Рядок, що містить найменше з отриманих значень, називається вирішуючим.

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

3) Будуємо другу симплексну таблицю 3.2.

Таблиця 3.2

a_i0j0 - вирішуючий елемент;

a_ij - колишній елемент;

a_i0j - елемент вирішуючого рядка;

a_ij0 - елемент вирішуючого стовпця;

a_ij1 = новий елемент =

4) План не оптимальний, тому що існують позитивні оцінки вільних змінних.

Будуємо нову таблицю 3.3, аналогічно попередній.

Таблиця 3.3

Оптимальний план задачі Х = (0,0,35,20,0,0,30). Оскільки оцінки вільних змінних індексного рядка останньої симплексної таблиці відмінні від нуля, то задача має єдине рішення Z = 5100 грн.

Лабораторна робота №4 Метод потенціалів розв’язування транспортної задачі Хід роботи.

Алгоритм знаходження оптимального рішення Т.3.

I. Знаходження початкового опорного плану (методами північно-західного кута, мінімальної вартості).

П. Побудова системи потенціалів.

Ш. Перевірка виконання умови оптимальності для незайнятих клітин ij =(ui+vj) - cij.

IV. Перехід до найкращого опорного плану:

1) вибір клітини, в яку необхідно зробити перехід;

2) побудова циклу та визначення величини перерозподілу вантажу;

3) контроль розрахунків.

Задача

Транспортна задача Л.П.

Умови в табл. 4.1

Таблиця 4.1

Виробники	Споживачі				Запас
	В1	В2	В3	В4
А1	4	6	7	2	200
А2	2	4	3	1	150
А3	9	7	4	2	150
Потреби	100	120	130	150	500

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

Таблиця 4.2

Виробники	Споживачі				Запас
	В1	В2	В3	В4
А1	4 100	6 100	7	2	200
А2	2 0	4	3	1 150	150
А3	9	7 20	4 130	2	150
Потреби	100	120	130	150	500

Будуємо систему потенціалів U_i, V_j, ( i =1,3, j=1,4), виходячи з умови U_i+V_j = C_ij для зайнятих кліток в опорному плані. Нехай U_i= 0, тоді V₁-U₁ = 4, V₄-U₂ = 1 , V₂-U₁ = 6, V₂-U₃ = 7, V₁-U₂ = 2, V₃-U₃ = 4, вирішивши цю систему, одержимо V₁ = 4, V₂ = 6, V₃ = 3, V₄ = 3, U₁=0, U₂=-2, U₃=1.

Обчислюємо значення _ij = (U_i+V_j )- C_ij для незайнятих кліток (записуємо в лівий нижній кут кліток), якщо всі _ij 0, то план оптимальний; якщо існують _ij> 0, то план не оптимальний і переходимо до побудови поліпшеного опорного плану.

₁₃ = (V₃+U₁)- C₁₃ = (3+0)-7 = -4<0; ₃₁ = -4<0; ₃₄ = 2>0

₁₄ = (V₄+U₁)- C₁₄ = (3+0)-2 = 1 >0; ₂₂ = 0; ₂₃ = -2<0

Серед оцінок є _ij >0, тому план не оптимальний. Знаходимо max { _ij } = max { ₁₄ ; ₃₄ }

VI. Будуємо цикл із вершинами в обраній клітці й позначаємо його вершини знаками.

Таблиця 4.3

 = min = = 20 – величина перерозподілу вантажу. Робимо зрушення по циклу на величину (табл. 4.4), переходимо до нового оптимального плану, перехід здійснюємо за формулою:

Х_ij – для кліток, що не входять у цикл;

Х_ij +  - для кліток, відзначених знаком “+”

Х_ij –  - для кліток, відзначених знаком “–”

Таблиця 4.4

Складаємо нову систему потенціалів (див. табл. 4.4). Знаходимо оцінки вільних кліток , вони записуються в лівому нижньому куті. Умова оптимальності порушується в клітці (1;3). Включаємо її в набір заповнених. Будуємо цикл перерахування (табл. 4.4) і робимо зрушення за циклом на величину поставки  = min = = 80 F = 1690.

Таблиця 4.5

Обчислення для табл. 4.5 аналогічні обчисленням для табл. 4.4.

Порушується оптимальність у клітці (2;2).  = min = = 50, робимо зрушення за циклом, на величину  = 50.

Таблиця 4.6

Обчислення в табл. 4.6 аналогічні обчисленням таблиць 4.4 й 4.5 Знайдений у таблиці опорний план оптимальний, тому що 0 F = 1640.

Відповідь:

Лабораторна робота №5

Двоїстість та її застосування в економічному аналізі

Хід роботи.

а) Для даних задач лінійного програмування побудувати двоїсті.

б) Розв’язати обидві задачі лінійного програмування за допомогою табличного симплекс-методу та за допомогою Microsoft EXCEL for WINDOWS (“Пошук рішень”).

в) Порівняти отримані розв’язки, знайти відповідність між ними

г) Проаналізувати виконання I основної теореми двоїстості.

Задача

Нехай початкова задача має вигляд:

(1.5)

(1.6)

Тоді двоїста задача до задачі (1.5) - (1.6) буде мати вигляд

(1.7)

(1.8)

Дамо деякі пояснення:

1) Кількість змінних у початковій задачі дорівнює кількості обмежень у двоїстій. А кількість обмежень початкової задачі дорівнює кількості двоїстих змінних.

2) Матриця коефіцієнтів системи обмежень (1.8) є транспонованою до матриці коефіцієнтів системи (1.6).

3) Коефіцієнти цільової функції початкової задачі (1.5) стають правими частинами системи обмежень (1.8).

4) Праві частини системи обмежень (1.6) стають коефіцієнтами цільової функції двоїстої задачі (1.7).

5) Пояснимо, як вибираються знаки в обмеженнях двоїстої задачі.

Якщо на змінну x_j початкової задачі накладено умова невід’ємності (x_j 0), то відповідне j-те обмеження двоїстої задачі буде нерівністю вигляду (оскільки двоїста задача розглядається на min).

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

6) Якщо цільова функція початкової задачі максимізується (max), то цільова функція двоїстої - мінімізується (min).

7) Якщо і-обмеження початкової задачі було нерівністю (у прикладі це перше обмеження), то відповідна двоїста змінна повинна бути невід’ємною, тобто y_i 0 (в прикладі y₁ 0).

Якщо ж у системі обмежень початкової задачі обмеження було рівністю, то відповідна двоїста змінна може бути будь-якою за знаком (у прикладі на y₂ не накладається умова невід’ємності).

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

Спочатку сформулюємо I основну теорему двоїстості:

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

f(x*)=z(y*);

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

Значення двоїстої оцінки знаходиться в останній симплекс-таблиці (1.1) на перетині рядка цільової функції з колонкою даної додаткової змінної плюс коефіцієнт цієї змінної в цільовій функції [1].

Розглянемо приклад:

f(x) =-5x₁+x₂+x₃ min f(x) =-5x₁+x₂+x₃+Mx₅ min

x₁+x₂ 4 чи x₁+x₂-x₄+x₅=4 - кононічний вигляд задачі

5x₁-x₂+x₃=14 5x₁-x₂+x₃=14

x_j 0 j= x_j 0 j=

Двоїста задача має вигляд :

z(y)=4y₁+14y₂-My₄ max

y₁+5y₂ -5 -y₁-5y₂-y₃+y₄=5

y₁-y₂ 1 чи y₁+y₂+y₅=1 - кононічний вигляд задачі

y₁ 0 y₂+y₆=1

y₂ 1 y_i 0, i=

Таблиця 5.1 Остання симплекс-таблиця при розв’язанні прямої задачі

Бn	Cб	B	P1	P2	P3	P4	P5
			-5	1	1	0	М
P2	1	1	0	1	-1/6	-5/6	5/6
P1	-5	3	1	0	1/6	-1/6	1/6
Оцінки цільової функції		-14	0	0	-2	0	М

З таблиці 1.1. маємо розв’язки відповідно прямої і двоїстої задачі:

x*=(3,1,0,0,0)

y*=(0,-1,0,0)

При цьому f(x*)=z(y*)=-14.

Лабораторна робота №6

Угорський метод розв’язання задачі про призначення

Хід роботи

Розв’язати задачу про призначення (на максимум) із заданою матрицею продуктивності праці С=(с_ij ) за допомогою угорського методу .

Задача

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

Необхідно виконати n ( ) робіт. Для цього використовуються n ( ) виконавців, кожний з яких спроможний виконувати будь-яку роботу. Відомі витрати cij на виконання i-ї роботи j-тим виконавцем. Потрібно призначити кожного виконавця на одну роботу так, щоб всі роботи були виконані і при цьому сумарні витрати повинні бути якнайменшими.

Позначимо: xij – змінна величина, що відбиває факт призначення, тобто

xij=

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

(1)

– цільова функція задачі, що відбиває загальні (сумарні) витрати,

обмеження задачі:

(2)

- кожна робота повинна бути виконаною,

- (3)

кожен робітник повинен бути задіяним на одній роботі,

. (4)

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

1. Розв’язок задачі не зміниться, якщо до будь-якого стовпця чи рядка матриці додати чи відняти деяке число, тобто якщо план x* – оптимальний план задачі (1)-(4), то він також є оптимальним для функції цілі Z’ з матрицею , де

, i=1,…,n, j=1,…,n, .

2. Якщо знайдений план x*, такий, що та всі , то x* -- оптимальний план.

Суть алгоритму угорського методу

Шляхом додавання певним чином знайдених чисел до деяких стовпців і відніманням їх з деяких рядків знаходять систему так званих незалежних нулів. Незалежними нулями називаються нулі, для яких виконується умова: ніякі два (чи більше) нулі не лежать на одній лінії. Якщо число незалежних нулів дорівнює n, то, прийнявши відповідні до них змінні xij рівними 1, а всі інші – рівними 0, відповідно до твердження 2, одержимо оптимальний план призначення.

Алгоритм складається з попереднього кроку і не більш, ніж (n-2) послідовно повторюваних ітерацій. На попередньому етапі у випадку рішення задачі на максимум, її перетворюють в еквівалентну задачу на мінімум. На цьому ж етапі виділяється система незалежних нулів. Кожна наступна ітерація спрямована на збільшення хоча б на 1 кількості незалежних нулів. Як тільки число незалежних нулів k стане рівним розмірності матриці nxn (тобто ), задача вирішена.

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

Приклад. Розв’язати задачу про призначення (на максимум) за допомогою угорського методу

,

Де

Підготовчий етап. Відшукуємо максимальний елемент у кожному зі стовпців матриці і віднімаємо кожен елемент матриці С з максимального елемента відповідного стовпця. В отриманій С’ відшукуємо мінімальний елемент у кожному з рядків і віднімаємо їх з відповідних елементів матриці С’: У результаті отримали матрицю С0

1). 2).

3).

Визначаємо початкову систему незалежних нулів, відзначаючи їх зірочками. Число незалежних нулів . Оскільки , то переходимо до основного кроку, що повторюється.

Перша ітерація. У матриці 4) над стовпцями, що містять 0*, ставимо знак «+». Знаходимо невиділений стовпець j=4. Шукаємо в невиділеному стовпці нульовий елемент. Це с14=0. Позначаємо його штрихом с14=0’. Переглядаємо рядок i=1. У ньому є виділений нуль с11=0*. Знімаємо виділення з першого стовпця знаком. « ». Виділяємо перший рядок знаком «+». Одержуємо матрицю 5).

4). + + + 5) + +

Якщо в матриці 5) викреслити виділені стовпці j=2,3 і виділений рядок, то одержимо матрицю, у якій немає нулів. Позначимо множину невиділених рядків через I1. Очевидно, що I1={2,3,4}, а множину невиділених стовпців через I2, тут I2={1,4}. Знаходимо мінімальний із невиділених елементів матриці: min{сij}=4, i I1, j I2..

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

6) + +

У результаті такого перетворення одержимо нові невиділені нулі С21=0, С41=0, С44=0. Беремо один з них і відзначаємо його штрихом. Наприклад, С21=0’. Так як в рядку i=2 є 0*, то знімаємо виділення зі стовпця j=3. Перейдемо до матриці 7):

7) +

Серед невиділених рядків та стовпців матриці є невиділений нуль. Це С41=0. Помічаємо цей нуль С41=0’. У рядку i=4 є 0*, знімаємо виділення над стовпцем j=2. Виділяємо рядок і=4. Одержуємо матрицю 8):

8).

Серед невиділених рядків знаходимо невиділений нуль С33=0. Помічаємо цей нуль С33=0’. У рядку i=3 немає 0*, тому потрібно будувати ланцюжок. Від останнього нуля зі штрихом С33=0’ по стовпцю переходимо до нуля із зірочкою С23=0*. Від С23=0* по рядку i=2 переходимо до нуля зі штрихом С21=0’. Від С21=0’ по стовпцю j=1 переходимо до нуля з зірочкою С11=0*. Від С11=0* переходимо по рядку i=1 до С14=0’. У стовпці j=4 немає 0*. Отже, побудова ланцюжка закінчена. Побудований ланцюжок показаний у матриці 9):

9).

На ланцюжку С33 С42 С21 С14 нулі зі штрихом замінюємо на нулі з зірочкою. Зірочки над нулями, що не знаходяться на ланцюжку, зберігаємо. Всі інші виділення знищуємо. Переходимо до матриці 10), у якій число незалежних нулів збільшується на одиницю. На цьому перша ітерація закінчується:

10)

Друга ітерація. Підраховуємо число незалежних нулів в матриці 10). Оскільки n=4, то k=n. Таким чином, задача розв’язана. Оптимальний план призначення представлений у матриці 11).

11). x*= .