ЛАБОРАТОРНА РОБОТА № 7. Цілочислове програмування.

Мета роботи: Навчитися складати модель задачі цілочислового програмування. Засвоїти алгоритм розв’язання задач цілочислового програмування методом відтинання площинами і методом розгалужень і границь.

Завдання: розв’язати задачі цілочислового програмування методом відтинання площинами і методом розгалужень і границь.

Хід роботи.

1.     Ознайомитись із теоретичними відомостями про цілочислове програмування і медодами розв’язання задач цілочислового програмування: методом Ґоморі (метод відтинання площинами) і комбінаторними методами (наприклад, методом розгалужень і границь).

2.     ЧАСТИНА 1. Розв’язати методом Ґоморі задачу цілочислового лінійного програмування, вибравши варіант з додатка 7, який відповідає порядковому номеру студента в списку групи.

3.     ЧАСТИНА 2. Нехай для виробництва використовуються два види ресурсів: матеріальні і трудові. Можливі варіанти використання ресурсів і отримання прибутку відомі. Визначити, які варіанти варто прийняти для реалізації за умови, що загальна кількість прийнятих варіантів не перевищує трьох. Розв’язати методом розгалужень і границь задачу вибору варіантів, вибравши варіант з додатка 8, який відповідає порядковому номеру студента в списку групи (таблиця 7.1).

Таблиця 7.1

Вихідні дані до задачі вибору варіантів

Показник	Варіант				Наявність ресурсів
	1	2	3	4
Прибуток	75	90	100	220	-
Ресурси:
матеріальні	300	280	340	350	1200
трудові	20	25	32	38	90

4.     Ввести булеві змінні. Прийняти, що -ому варіанту відповідає змінна (=0; 1). При цьому = 1, якщо -ий варіант приймається, і = 0, якщо -ий варіант не приймається.

5.     На основі даних індивідуального завдання побудувати модель задачі цілочислового програмування:

;

; (а)

; (б)

. (в)

6.     Результати розв’язання задачі подати у вигляді таблиці (таблиця 7.2).

Таблиця 7.2

Розрахунок цільової функції та обмежень для різних комбінацій змінних

для задачі вибору варіантів

Варіант	Змінні				Умови			Прибуток
					(а)	(б)	(в)
1	0	0	0	0	0	0	0	0
2	1	0	0	0	300	20	1	75
3	0	1	0	0	280	25	1	90
4	0	0	1	0	340	32	1	100
5	0	0	0	1	350	38	1	220
6	1	1	0	0	580	45	2	165
7	0	1	1	0	620	57	2	190
8	0	0	1	1	690	70	2	320
9	1	0	1	0	640	52	2	175
10	1	0	0	1	650	58	2	295
11	0	1	0	1	630	63	2	310
12	1	1	1	0	920	77	3	265
13	0	1	1	1	970	95	3	410
14	1	1	0	1	930	83	3	385
15	1	0	1	1	990	90	3	395
16	1	1	1	1	1270	115	4	485
Вимоги	-	-	-	-

7.     Визначити, які варіанти слід відкинути через те, що не виконуються необхідні умови обмежень у моделі. Наприклад, у розглянутому прикладі варіанти під номерами 13 і 16 слід відразу відкинути, оскільки не виконується вимога обмеження (в) для варіанта №16 і вимога обмеження (б) для варіанта №13.

8.     Із варіантів, які залишились, вибрати той, при якому цільова функція набуває максимального значення. Наприклад, у розглянутому прикладі це варіант №15 ().

9.     Записати характеристики оптимального варіанту. Наприклад, у розглянутому прикладі: ; ; ; ; .

10. Зробити висновки.

Додаток 7

Вихідні дані для лабораторної роботи № 7

Частина 1

Метод Ґоморі (метод відтинання площинами)

Варіант 1

;

,

,

;

, х₁, х₂ – цілі.

Варіант 2

;

,

,

;

, х₁, х₂ – цілі.

Варіант 3

;

,

,

;

, х₁, х₂ – цілі.

Варіант 4

;

,

,

;

, х₁, х₂ – цілі.

Варіант 5

;

,

,

;

, х₁, х₂ – цілі.

Варіант 6

;

,

,

;

, х₁, х₂ – цілі.

Варіант 7

;

,

,

;

, х₁, х₂ – цілі.

Варіант 8

;

,

,

;

, х₁, х₂ – цілі.

Варіант 9

;

,

,

;

, х₁, х₂ – цілі.

Варіант 10

;

,

,

;

, х₁, х₂ – цілі.

Варіант 11

;

,

,

;

, х₁, х₂ – цілі.

Додаток 8

Вихідні дані для лабораторної роботи № 7

Частина 2

Метод розгалужень і границь

Варіант i (i - порядковий номер студента у списку групи)

Показник	Варіант				Наявність ресурсів
	1	2	3	4
Прибуток	75+3* i	90- 2*i	100* i	220* i	-
Ресурси:
матеріальні	300- i	280+ i	340- i	350+ i	1200
трудові	20+ 2*i	25- i	32- 2*i	38+ i	90