ММДО_МУ по ПЗ(+)

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

МЕТОДИЧНІ ВКАЗІВКИ

до практичних занять з дисципліни

«МАТЕМАТИЧНІ МЕТОДИ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ, ДОСЛІДЖЕННЯ ОПЕРАЦІЙ»

для студентів усіх форм навчання напрямків 6.050101 «Комп’ютерні науки»,

6.050102 «Комп’ютерна інженерія та управління»

ЗАТВЕРДЖЕНО

кафедрою штучного інтелекту Протокол №8 2.12.08.

Харків 2009

Методичні вказівки до практичних занять з дисциплін «Математичні методи дослідження операцій», «Дослідження операцій» для студентів усіх форм навчання напрямків 6.050101 «Комп’ютерні науки», 6.050102 «Комп’ютерна інженерія та управління» / Упоряд.: А.М. Гвоздинський, В.О. Губін, В.Л. Шергін – Харків; ХНУРЕ, 2009. – 36с.

Упорядники: А.М. Гвоздинський В.О. Губін В.Л. Шергін

Рецензент В.П. Авраменко, д-р техн.. наук, професор каф. ІУС

ЗМІСТ

Загальні положення………………………………………………………………………………..4 1 Задачі лінійного програмування………………………………………………………………..4

1.1Постановка та форми запису задач лінійного програмування (ЗЛП)……………………4

1.2Геометрична інтерпретація ЗЛП……………………………………………………………7

1.3Симплексний метод розв’язання ЗЛП…………………...………………………………..12

1.4Розв’язання ЗЛП з будь-яким видом обмежень…………………………………………..18

1.5Контрольні запитання і завдання………………………………………………………….23

2 Спеціальні методи розв’язання ЗЛП ......................................................................................

23

2.1Знаходження початкового опорного плану транспортної задачі………………………..23

2.2Метод потенціалів…………………………………………………………………………..27

2.3Задачі про призначення…………………………………………………………………….33

2.4Контрольні запитання і завдання…………………………………………………………..38

Перелік посилань………………………………………………………………………………….39

ЗАГАЛЬНІ ПОЛОЖЕННЯ

Дані методичні вказівки складені відповідно до програми дисциплін «Математичні методи дослідження операцій», «Дослідження операцій», що вивчають студенти напрямків «Комп’ютерні науки», «Комп’ютерна інженерія та управління», і мають використовуватися для проведення практичних занять та комплектування домашніх практичних занять даного курсу.

Методичні вказівки складаються з двох частин. Мета першої частини – закріплення теоретичного матеріалу та оволодіння практичними навичками розв’язання задач лінійного програмування різноманітними методами. У даній частині методичних вказівок розглядається симплекс-метод та графічний метод розв’язання задач лінійного програмування. У другій частині здійснюється закріплення теоретичних знань та розвиток практичних навичок розв’язання задач транспортного типу.

Методичні вказівки містять короткі теоретичні відомості, приклади розв’язання задач, контрольні запитання та завдання, варіанти індивідуальних домашніх завдань.

1 ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

1.1 Постановка та форми запису задач лінійного програмування (ЗЛП)

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

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

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

Нехай є n видів прикладів Пі, = ̅̅̅̅̅1, , які можна комбінувати, складаючи устаткуваня лабораторії. Кожен з цих видів приладів має виконувати певний набір процедур для функціонування лабораторії. Набори процедур, що виконують окремі прилади, задаються матрицею aij, де aij означає продуктивність приладу, тобто кількість процедур Qi, що виконуються за день приладом Пі, причому кожний прилад здатен виконувати протягом дня тільки один вид процедур.

Задаються денні норми, тобто необхідна кількість процедур кожного виду, що мають виконуватись лабораторією за день Nj, вартість кожного виду приладів Сі, =

̅̅̅̅̅1, , існуючі запаси кожного виду приладів Bі (максимально

припустима заявка на кожний вид приладів), максимально припустимі кількості приладів даного виду у лабораторії Si.

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

( ) = ∑

=1

і задовольняв би перерахованим обмеженням:

∑ ≥ , ≥ ≥ 0, ≤

=1

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

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

Після ознайомлення з конкретним прикладом розглянемо загальну постановку типової ЗЛП, математичне формулювання якої здійснюється так: потрібно знайти такі значення х1 ,х2 …, хn, які задовольняють системні співвідношення вигляду

				+		+ +
		11	1	12	2	1			1
		21		+		+ +
			1	22	2	2			2
			-	-----------------------------------						(1.1)
				+		+ +
	1 1			2	2

= {=, ≤, ≥}, = ̅̅̅̅̅̅1,

і з цим визначили б найбільше (найменьше) значення функції

	(1.2)

( 1, 2, … , ) = ∑ ,

=1

де bi, ci, ai – задані сталі величини.
Будь-який упорядкований набір ( ̅ , ̅̅̅,	… , ̅̅̅), значень змінних, що
1 2

задовольняє усім обмеженням (1.1), називають припустимим розв’язанням або планом задачі. Множина всіх припустимих рішень називається припустимою множиною задачі.

Припустиме розв’язання ( ,	, … , ), що що надає цільовій функції
1 2

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

Існують різні форми запису ЗЛП: загальна, стандартна, канонічна, матрична та векторна.

Загальна форма має такий вигляд:

	( ) = ∑		→
					(1.3)
	=1
				̅̅̅̅̅
	∑ = , = 1, ,				(1.4)
	=1
				̅̅̅̅̅̅̅̅̅̅
	∑ ≤ , = + 1, ,				(1.5)
	=1
				̅̅̅̅̅̅̅̅̅̅
	∑ ≥ , = + 1,				(1.6)
	=1
	̅̅̅̅			̅̅̅̅̅̅̅̅̅	(1.7)
	≥ 0, = 1, , ≤ 0, = + 1, , ≤

З виразів (1.3)-(1.7) робимо висновок, що загальна форма ЗЛП є задачею на знаходження екстремуму лінійної цільової функції за умов системних лінійних обмежень, що містять як рівності, так і нерівності обох знаків, і за невідомих змінних, з яких одні пов’язані умовами невід’ємності, а знак решти жодних обмежень не ускладнено.

У стандартній формі ЗЛП потрібно знайти екстремум цільової функції за системою обмежень-нерівностей та умовою невід'ємності всіх змінних, тобто математична модель набуває такого вигляду:

( ) = ∑			→		(1.8)
=1
				̅̅̅̅
∑ ≤ , = 1, ,					(1.9)
=1
				̅̅̅̅̅̅̅̅̅̅
∑ ≤ , = + 1, ,					(1.10)
=1
				̅̅̅̅̅	(1.11)
	≥ 0, = 1,

Існує так звана канонічна форма запису ЗЛП, яка полягає у знаходженні екстремуму цільової функції за системою обмежень-рівнянь і умовою невід'ємності всіх змінних:

( ) = ∑		→		(1.12)
=1
			̅̅̅̅̅̅
∑ ≤ , = 1, ,				(1.13)
=1
			̅̅̅̅̅	(1.11)
≥ 0, = 1,

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

обмежень-нерівностей на систему обмежень рівнянь шляхом додання нової

невід’ємної змінної

,

̅̅̅̅

до кожної лівої частини нерівностей (1.9). Такого ж

= 1,

+1

самого результату досягаємо, віднімаючи від кожної лівої частини нерівностей (1.10)

нову невід'ємну змінну

̅̅̅̅̅̅̅̅̅̅

перетворюючи їх також на систему

≥ 0, = + 1, ,

+1

рівнянь.

Більш компактний запис задач досягається у матричній формі

( ) = → max( )

(1.15)

= ,

(1.16)

≥ 0,

(1.17)

або у ще більш компактному вигляді

max( | = ; ≥ 0)

(1.18)

Існує також так звана векторна форма запису канонічної ЗЛП. Введемо

позначення:

11

11

1

= ‖

21

‖

;

= ‖

12

‖ ; … ; = ‖

2

‖ ;

1

(1.19)

= ‖ 2 ‖.

1

…

2

…

…

0

…

1

2

Тоді задача набуває такого вигляду:

( ) = =

∑ → ,

(1.20)

=1

∑

= ,

(

1.21

)

0

=1

̅̅̅̅̅

(1.22)

≥ 0, = 1,

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

мінімізації, змінивши знак цільової функції на протилежний, тобто:

max ( ) = (− ( )).

(1.23)

1.2 Геометрична інтерпретація ЗЛП

Мета заняття - набуття практичних навичок розв'язання задач лінійного програмування геометричним методом.

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

Яку б вимірність не мав вектор невідомих Х=(х1,х2,…,хn) канонічної форми ЗЛП, вимірність багатогранника планів задачі завжди визначається кількістю незалежних невідомих, тобто різницею між кількістю невідомих і рангом системи обмежень: k=n-r, r=m, r_ранг матриці.

Розглянемо випадок, коли кількість змінних n на дві більше, ніж кількість незалежних рівнянь m, яким вони мають відповідати, тобто n-m=2.

Тоді, як ми вже знаємо, можна дві з n змінних припустимо X1, Х2, обрати як вільні, а решту m зробити базовими і виразити їх через вільні. Припустимо, що це зроблено. Отримаємо m=п-2 рівнянь вигляду:

	3 = 31 1 + 32 2 + 3;
	4	= 41 1 + 42 2			+ 4;	(1.24)
	− − − − − − − − − − −
		=	+		+ .
		1	1	2 2

Дамо ЗЛП геометричну інтерпретацію. У системі координат на площині відкладатимемо значення вільних змінних. Оскільки змінні x1, х2, мають бути невід’ємні, припустимі значення вільних змінних розташовані вище осі ОХ1 та праворуч осі ОХ2. Останні змінні х3,х4,…,хn також мають бути невід’ємні, тобто мають винувати умови

	3 = 31 1 + 32 2 + 3 ≥ 0;
	4 = 41 1 + 42 2 + 4 ≥ 0;
	− − − − − − − − − − −							(1.25)
		=		+		+	≥ 0.
		1	1		2 2
Якщо у будь-якій нерівності в системі (1.25) взяти її рівною нулю, то
отримаємо
	=	+		+ = 0,			̅̅̅̅̅	(1.26)
							= 3,
	1	1	2	2
Це є рівняння прямої, що є граничною між півплощиною існування усіх								≥ 0 і
півплощиною, де < 0.
Здійснюючи побудову всіх цих прямих у системі координат х1ох2 і відмічаючи
штрихуванням той бік прямих,			де > 0,			отримаємо опуклий багатокутник,		який

утворює область припустимих рішень (ОПР). Отже виникає запитання про знаходження оптимального розв’язання із припустимих. Дамо і цій задачі геометричну інтерпретацію, причому знову для випадку, коли m=n-2. Знову припустимо, що вільні змінні є х1 та х2, а базисні х3, х4,…,хn, що виражені через вільні за виразами (1.24).

Аналогічно виконаємо перетворення і цільової функції, внаслідок чого

отримаємо:
= +	+	(1.27)
1 1	2 2

де – вільний член, що з’явився внаслідок перетворення цільової функції. Вочевидь, лінійна форма (1.27) досягає екстремуму з тими ж значеннями х1 та

х2, що і функція

′ =		+		(1.28)
1	1	2	2

Знайдемо х1 та х2, користуючись геометричною інтерпретацією. Дамо ′ деяке стале значення С.

= 1 1 + 2 2 = С

(1.29)

Отримаємо рівняння прямої на площину х1ох2. Кутовий коефіцієнт цієї прямої= = −1/2, а відрізок, що відсікає вона на осі, ох2 – С/ 2. Якщо ми змінимо С на С1, кутовий коефіцієнт не зміниться, а пряма переміститься паралельно сама до себе в нове положення ′ = 1. Отже значенню ′ відповідають різні прямі на площині, але всі вони паралельні між собою . замість у сіх цих прямих достатньо зобразити на площині одну, основну пряму, наприклад, ′ = 0, а потім можна перемішувати її паралельно саму до себе. При переміщенні в один бік ′ зростатиме, а у другий – зменшуватиметься.

Побудуємо пряму ′ = 0 на площину х1ох2. Її кутовий коефіцієнт −1/2. Для цього на осі абсцис відкладемо відрізок 2, а на осі ординат відрізок - 1. На площині отримаємо деяку точку А з координатами 1 та 2. Провівши через початок координат та точку А пряму, отримаємо геометричне зображення прямої на площині′ = 0. Тепер залишається з’ясувати, в який бік паралельно до себе потрібно переміщувати цю пряму, щоб величина ′ зменшувалася (зростала). Нахил цієї прямої відносно системи координат визначається знаками коефіцієнтів 1 та 2.

Дамо тепер геометричну інтерпретацію знаходження оптимального розв’язання ЗЛП серед припустимих.

Нехай ми маємо збудувати ОПР і пряму ′ = 0 і нам відомий напрямок потрібного нам зменшення (зростання) ′. При переміщення основної прямої у певному напрямку ′ змінюватиметься. Очевидно, що екстремального значення вона досягне, коли пряма проходитиме через крайню точку ОПР, найбільш віддалену від початку координат. Схрещення цієї прямої з однією із вершин дає координати цієї точки х1 і х2, які й визначають оптимальне розв’язання ЗЛП. Знаючи значення х1 і х2 можна знайти, підставляючи їх у (1.24) і (1.28), оптимальні значення х1, х2,…,хn, а

також extremum ′.

Під час підготовки до заняття потрібно вивчити теоретичний матеріал,

викладений в [1, с. 89-95; 2. с. 55-63; 3. с. 27-31].

Припустимо, що задача вже перетворена на вирази через вільні змінні і має вигляд:

( ) = 71 + 52 → ; 21 + 32 ≤ 18; 21 + 2 ≤ 13;

1 + 2 ≥ 3; 0 ≤ 2 ≤ 5; 1 ≥ 0.

На базі системи обмежень–нерівностей будуємо ОПР. Спочатку цю систему перетворимо на систему рівнянь шляхом введення додаткових (базисних) змінних. У результаті отримаємо

2 1 + 3 2 + 3 = 18; 2 1 + 2 + 4 = 13;1 + 2 − 5 = 3;2 + 6 = 5;1 ≥ 0; 2 ≥ 0.

Продовжимо перетворення:

3 = 18 − 2 1 − 3 2 = 04 = 13 − 2 1 − 2 = 05 = 3 − 1 − 2 = 06 = 5 − 2 = 0

1 ≥ 0; 2 ≥ 0

І далі

1/9 + 2/6 = 11/6,5 + 2/13 = 1

1/3 + 2/3 = 12/5 = 1

Виконаємо геометричну розбудову ОПР (рис. 1.1).

Рисунок 1.1 – Геометричне розв’язання ЗЛП