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

Метод складається з однотипних кроків, тому його формальний виклад дамо лише для 1-го кроку. Заповнюємо пiвнiчно-захiдну клітинку таблиці, покладаючи x11 = min{ a1, b1 }. Можливі три випадки:

1. a1 < b1, тоді x11 = a1 i викреслюється 1-й рядок таблиці;

2. a1 > b1, тоді x11 = b1 i викреслюється 1-й стовпець таблиці;

3. a1 = b1, тоді x11 = a1 = b1 i викреслюється як 1-й рядок, так i 1-й стовпець. В останньому випадку в одну з викреслених клітинок заноситься нульове базисне перевезення (відповідний вихідний допустимий базисний розв'язок буде виродженим).

В усіх випадках після заповнення базисної клітинки об'єми запасів a1 i потреб b1 зменшують на величину, що дорівнює x11. Кiнець кроку.

На кожному з наступних кроків розглядається «обрізана» транспортна таблиця, тобто викреслені рядки i стовпцi ігноруються.

Задача 7.

Побудувати опорний план ТЗ (або вихідний ДБР):

Таблиця 2

	Q1	Q2	Q3	Q4	Q5	a
P1
P2
P3
P4
B

Заповнення починається з клітинки . Оскільки , то викреслюється перший рядок таблиці, . Переходимо до клітинки . Заносимо в клітинку і викреслюємо перший стовпчик, . Переходимо до клітинки : , викреслюється другий рядок, . Наступною буде клітинка : , викреслюємо другий стовпчик, . Переходимо до клітинки : , викреслюється третій рядок, . Переходимо до клітинки : , . Наступна клітинка : , . Остання клітинка : , .

Таблиця 3

	Q1	Q2	Q3	Q4	Q5	a	a-x
P1
P2
P3
P4
B
b-x

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

Метод мінімального елемента

Кількість ітерацій при розв’язуванні ТЗ можна скоротити, якщо перший опорний план будувати за методом мінімального елемента.

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

Задача 7.

Розв’яжемо задачу 7 з попереднього пункту методом мінімального елемента.

На кожному кроцi вибирається клітинка з найменшим значенням транспортних витрат cij. Оскільки , то заповнення починається з клітинки : , викреслюється перший рядок таблиці, . Переходимо до клітинки . Заносимо в клітинку і викреслюємо другий рядок, . Переходимо до клітинки : , викреслюється третій стовпчик, . Наступною буде клітинка : , викреслюємо третій рядок, . Переходимо до клітинки : , викреслюється п’ятий стовпчик, . Переходимо до клітинки : , викреслюється четвертий стовпчик, . Наступна клітинка : , викреслюється другий стовпчик, . Остання клітинка : , .

Таблиця 4

	Q1	Q2	Q3	Q4	Q5	a	a-x
P1
P2
P3
P4
B
b-x

Очевидно, що цей опорний план є ефективнішим за план, наведений у табл.2.

Метод викреслювання

 

Метод застосовується при побудові циклу. На кожному кроцi методу в транспортній таблиці викреслюється або рядок, або стовпець, які в подальшому ігноруються. Викреслювати належить рядки (стовпцi), які мають тільки одну базисну клітинку. Невикресленi клітинки транспортної таблиці утворюють цикл.

Метод подвійної переваги

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

 

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

Алгоритм методу потенціалів

1. Знаходиться вихідний допустимий базисний розв'язок (ДБР), наприклад, за допомогою одного із згаданих вище методів.

2. В подальшому метод потенціалів складається з однотипних кроків, на кожному з яких:

i) Обчислюються потенціали рядків ui, i=1,...,m, i стовпцiв vj, j=1,...,n, транспортної таблиці як розв'язок системи vjui = cij, де i та j приймають такі значення, що клітинки (i,j) базисні.

ii) Обчислюються оцінки змінних xij для всіх небазисних клітинок (i,j) за формулою ij = cijvj + ui (оцінки базисних змінних нульові).

iii) Знайдені оцінки ij перевіряються на невiд'ємнiсть. Якщо всі ij0, i=1,...,m, j=1,...,n, то поточний ДБР оптимальний. Інакше переходять до поліпшення ДБР (пункт iv)).

iv) Визначають клітинку (k,l) з мінімальною від'ємною оцінкою, i приєднують її до сукупності базисних. Знаходять цикл (наприклад, методом викреслювання). Подiляють цикл на додатний i від'ємний пiвцикли, послідовно позначаючи клітинки - вершини циклу знаками «+» i «», починаючи з клітинки (k,l), яку першою відносять до додатного пiвциклу, наступну за нею до від'ємного, третю до додатного i т. д. Серед клітинок від'ємного пiвциклу визначають клітинку (s,r) з мінімальною величиною перевезення xij (якщо таких клітинок кілька, то вибирають тільки одну з них). Покладають = xsr. Збiльшують на значення перевезення xij в клітинках додатного пiвциклу i зменшують їх на те ж значення в клітинках від'ємного пiвциклу. В результаті здійснення вказаних процедур клітинка (k,l) вводиться до сукупності базисних, а клітинка (s,r) перестає бути базисною (на ній розривають цикл). Кiнець кроку.

Задача 8. Методом потенціалів ТЗ, дані для якої наведені в таблиці 2. З таблиці 4 візьмемо і початковий базисний розв’язок, побудований методом мінімального елемента. Усі ці дані перенесені в таблицю 5.

Таблиця 5

	Q1	Q2	Q3	Q4	Q5	a	u
P1	0 3	3 5	0 1	6 7	8 8
P2	0 2	3 4	4 4	8 8	10 9
P3	0 4	0 3 15 +	0 2 6 -	6 8	4 5		-1
P4	0 6	0 5 7 -	-1 3 +	0 4	0 3		-3
B
V

Крім цього до таблиці 5 занесені потенціали (останній стовпець), (останній рядок), що є розв’язком системи - базисне, де покладено У верхніх лівих кутах кожної з клітинок записані величини . Бачимо, що розглядуваний базисний розв’язок не є оптимальним.

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

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

Таблиця 6

	Q1	Q2	Q3	Q4	Q5	a	u
P1	-1 3 +	2 5	0 1 17 -	5 7	7 8
P2	0 2	3 4	5 4	8 8	10 9
P3	0 4	0 3 21	1 2	6 8	4 5
P4	0 6 5 -	0 5	0 3 6 +	0 4	0 3		-2
B
V

Таблиця 7

	Q1	Q2	Q3	Q4	Q5	a	u
P1	0 3	2 5	0 1	5 7
P2	0 2	2 4	4 4	7 8	9 9
P3	1 4	0 3	1 2	6 8	4 5
P4	0 6	0 5	0 3 11	0 4	0 3		-2
B
V

 

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

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

є оптимальним розв’язком ТЗ,

Завдання для самостійної роботи

для студентів заочної та денної форми навчання:

 

Завдання1. Графічним методом визначити оптимальні розв’язки ЗЛП.

 

1.1.

1.2.

1.3.

1.4.

1.5.

1.6.

 

1.7.

 

1.8.

 

 

1.9.

 

 

1.10.

 

 

1.11.

 

1.12.

 

1.13.

 

1.14.

 

 

1.15.

1.16.

 

 

1.17.

 

1.18.

 

1.19.

 

 

1.20.

 

1.21.

 

1.22.

 

1.23.

 

1.24.

 

1.25.

 

1.26.

 

1.27.

1.28.

 

1.29.

 

1.30.

 

1.31.

 

1.32.

 

1.33.

1.34.

1.35.

1.36.

1.37.

1.38.

 

Завдання 2. Розв’язати симплекс-методом ЗЛП. В усіх задачах, що пропонуються нижче, всі змінні невід’ємні.

2.1. 2x₁+x₂-x₃-x₄®min

x₁+x₂+2x₃-x₄=2

2x₁+x₂ -3x₃+x₄=6

x₁+x₂+ x₃ +x₄=7

2.2. 2x₁-4x₂®min

8x₁ -5x₂£16

x₁+3x₂³2

2x₁ +7x₂£9

2.3. 7x₁+5x₂®max

7x₁+5x₂³7

7x₁ -5x₂³35

x₁ - x₂£0

2.4. x₁-2x₂+3x₃®min

2x₁+3x₂ +4x₃=1

-2x₁+ x₂ +3x₃=2

2.5. 2x₁-3x₂®max

5x₁+2x₂³10

x₁+3x₂£12

2.6. 6x₁+4x₂®min

2x₁+x₂³3

x₁ -x₂£1

2.7. 4x₁+5x₂+9x₃+11x₄®max

x₁+ x₂+ x₃+ x₄ £15

7x₁+5x₂+ 3x₃+ 2x₄£80

3x₁+5x₂+10x₃+15x₄£60

2.8. x₁ - x₂-2x₃ +x₄®max

2x₁+ x₂+ 2x₃ -x₄ =2

-3x₁+ x₂ +2x₃+x₄ =6

x₁+ x₂+ x₃+x₄ =7

2.9. 4x₁+ x₂-2x₃ -x₄- x₅®min

x₃ -x₄+ x₅=1

x₂ +2x₄ -x₅=1

x₁+2x₂+ 2x₅=4

2.10. x₁+2x₂ +3x₃-x₄®max

x₁+2x₂+ 3x₃ =15

2x₁+ x₂ -3x₃ =20

x₁+ 2x₂+x₄ =10

2.11.

 

 

2.12.

 

 

2.13.

 

 

2.14.

 

2.15.

 

2.16.

 

2.17.

 

 

2.18.

 

2.19.

2.20.

 

2.21.

 

2.22.

 

2.23.

 

2.24.

 

2.25.

 

 

2.26.

 

 

2.27.

 

 

2.28.

 

2.29.

 

 

2.30.

 

2.31.

 

2.32.

 

2.33.

 

Завдання 3.

2.34.

 

2.35.

 

 

2.36.

 

 

2.37.

 

 

2.38.

 

 

У наведених задачах записати двоїсту задачу до поставленої ЗЛП.

 

3.1.

 

 

3.2.

3.3.

 

3.4.

3.5.

3.6.

3.7.

3.8.

3.9.

 

 

3.10.

3.11.

3.12.

 

3.13.

 

3.14.

3.15.

3.16.

3.17.

 

3.18.

3.19.

3.20.

3.21.

3.22.

3.23.

3.24.

3.25.

 

3.26.

3.27.

3.28.

3.29.

3.30.

3.31.

3.32.

3.33.

3.34.

Завдання 4. Розв'язати двоїстим симплекс-методом ЗЛП. В усіх задачах, що пропонуються далі, всі змінні невід'ємні.

 

4.1.	6 x1+ 4 x2 ® min,
	2 x1+ x2 ³ 3,
	x1– x2 £ 1,
	– x1+ 2 x2 ³ 1;
4.2.	2x1+ 3 x2 ® min,
	x1+ 5 x2 ³ 16,
	3 x1+ 2 x2 ³ 12,
	2 x1+ 4 x2 ³ 16;
4.3.	–6x1–4 x2 ® max,
	2 x1+ x2 ³ 3,
	x1– 2 x2 £ 2,
	3 x1+ 2 x2 ³ 1;
4.4.	6x1+ 4 x2 ® min,
	2 x1+ x2 ³ 3,	<