1.4. Завдання до контрольної роботи

Побудувати математичні моделі задач, які вибираються з табл. 31 згідно з варіантом.

Таблиця 31

На “4”		На “5”
Номер варіанта	Завдання	Номер варіанта	Завдання
1	7, 10, 11	13	23, 29, 51
2	8, 12, 13	14	11, 18, 52.1
3	9, 18, 21	15	10, 42, 49
4	19, 22, 34	16	23, 49, 47
5	20, 35, 40	17	13, 51, 52.2
6	29, 36, 42	18	22, 33, 48
7	37, 41, 51	19	21, 41, 44
8	11, 38, 48	20	12, 29, 39
9	12, 43, 49	21	11, 20, 33
10	10, 21, 35	22	19, 32, 51
11	13, 22, 45	23	18, 28, 42
12	19, 40, 43	24	13, 23, 40
		25	10, 22, 46

2. Гpафічний спосіб pозв’язання злп

2.1. Загальні положення графічного способу розв’язання злп

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

	,	(1)
за умов	;	(2)
	.	(3)

Кожна з нерівностей системи обмежень (2)-(3) геометрично визначає півплощину відповідно до граничних прямих (i = 1, ..., m), ,. У випадку, якщо система обмежень (2)-(3) є сумісною, областю її розв’язків є множина точок, які належать усім вказаним півплощинам. У загальному випадку область допустимих розв’язків задачі (1)-(3) являє собоюопуклий багатокутник. Сторони цього багатокутника лежать на прямих, рівняння яких отримуються з початкової системи обмежень заміною знаків нерівностей на знаки точних рівностей.

Таким чином, початкова ЗЛП полягає в знаходженні такої точки багатокутника розв’язків, в якій цільова функція z набуває максимального значення. Ця точка існує тоді, коли багатокутник розв’язків не порожній і на ньому цільова функція обмежена зверху. При вказаних умовах в одній з вершин багатокутника розв’язків цільова функція набуває максимального значення. Для знаходження цієї вершини побудуємо лінію рівня (деh – деяка константа), яка проходить через багатокутник розв’язків, і будемо пересувати її у напрямку вектора (нормалі) доти, поки вона не пройде через останню її спільну точку з багатокутником розв’язків. Координати вказаної точки і визначають оптимальний розв’язок даної задачі.

Область допустимих розв’язків (ОДР) системи нерівностей (1)-(3) може бути порожньою, однією точкою, відрізком, променем, опуклим багатокутником або необмеженою областю.

У випадку, коли система обмежень включаэ в себе обмеження-рівняння,

	,
	,
	,

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

На рис.3-6 наведені деякі випадки, які можуть трапитися при знаходженні розв’язку задачі (1)-(3).

Рис. 3 Рис. 4

Рис. 3 характеризує випадок, коли цільова функція набуває максимального значення в єдиній точці. З рис. 4 видно, що максимального значення цільова функція набуває у будь-якій точці відрізка AB (пряма цільової функції паралельна обмеженню, зображеному прямою АВ). У подібних випадках кажуть, що задача має альтернативний оптимум.

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

У випадку необмеженої області максимум (мінімум) функції z або не існує, якщо z не обмежена зверху (знизу), або досягається принаймні в одній з вершин області. На рис. 5 зображено випадок, коли цільова функція не обмежена зверху на множині допустимих розв’язків, а на рис. 6 – випадок, коли система обмежень є несумісною.

Рис. 5 Рис. 6

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

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

1. Побудова граничних прямих, рівняння яких отримуються в результаті заміни в обмеженнях (2) та (3) знаків нерівностей на знаки точних рівностей.

2. Знаходження півплощин, визначених кожним з обмежень задачі.

Для визначення, в який бік від граничної прямої розміщується півплощина, відповідна заданому обмеженню, досить перевірити одну будь-яку точку (простіше за все – точку (0, 0)). Якщо при підстановці її координат у ліву частину нерівності вона задовольняється, то точка, що перевіряється, належить півплощині. Якщо ж нерівність не задовольняється, то точка, що перевіряється, не належить півплощині (лежить у протилежному боці). Напрямок півплощини зображається знаком “” або штриховкою. (Нерівностям ітакож відповідає півплощина).

3. Знаходження багатокутника розв’язків.

4. Побудова вектора .

5. Побудова прямої , яка проходить через багатокутник розв’язків.

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

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

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