Міністерство освіти і науки україни

Національний університет “Львівська політехніка”

Кафедра САПР

Розв’язання та аналіз задач булевого програмування за допомогою Excel Методичні вказівки

до лабораторної роботи № 9

з курсу “Математичні методи дослідження операцій” для студентів базових напрямків

6.050101 “Комп’ютерні науки”

ЗАТВЕРДЖЕНО

на засіданні кафедри

“Системи автоматизованого проектування”

Протокол № 1

від “ 22 ” серпня 2011 р.

Львів 2011

РОЗВ’ЯЗАННЯ ТА АНАЛІЗ ЗАДАЧ БУЛЕВОГО ПРОГРАМУВАННЯ ЗА ДОПОМОГОЮ EXCEL. Методичні вказівки до лабораторної роботи № 9 з курсу “Математичні методи дослідження операцій” для студентів базових напрямків 6.050101 “Комп’ютерні науки” // Укл. Марікуца У.Б.

Укладачі:

Марікуца У.Б., доцент

Рецензенти:

Каркульовський В.І., к.т.н., доцент

Відповідальний за випуск:

Ткаченко С.П., к.т.н., доцент

Мета роботи: Вивчити метод розв’язання задач булевого програмування в Solver.

1. Теоретичні відомості.

1.Рішення задач з булевими змінними.

Частковим випадком задачі цілочисельних змінних являються задачі, в результаті рішення яких шукані зміні x_j можуть приймати не любі цілі значення, а тільки одне з двох: або 0, або 1. Ці змінні, щоб їх відрізняти від звичайних, будемо позначати _j замість x_j. Такі зміні на честь запропунувавшого їх англійського математика Джорджа Буля називаютьб булевими.

Розповсюдженної задачею з булевими змінними являється задача вибору варіантів із числа заданих.

Розглянемо таку задачу на прикладі. Є 4 варіанта використання ресурсів. Прибуток, який приносить кожний варіант, і ресурси як потребуються, таке і ті, якими володіють, приведені на мал.1.

Варіанти	1	2	3	4	Наявність
Прибуток	70	80	90	210	--------
Трудові	10	15	22	28	50
Фінанси	200	180	240	250	650

Мал.1.

Потрібно вибрати такі варіанти, щоб сумарний прибуток був максимальним.

Приймаємо, що

Тоді математична модель задачі буде мати вигляд:

F=70 ₁+80 ₂+90 ₃+210 ₄ max

10 ₁+15 ₂+22 ₃+28 ₄ 50

200 ₁+180 ₂+240 ₃+250 ₄ 650 (1)

0 _j 1; j=

_j- цілі.

Подивимось, як вирішується така задача.

Алгоритм. Рішення задачі з булевими змінними

1. Для вводу умов задачі скласти форму і ввести початкові дані (мал.2).

2. Сервіс, Пошук рішення…

На екрані: діалогове вікно Пошук рішення.

		Змінні
ім'я	1	2	3	4
Значення	0	0	0	0
Нижн.гр.	0	0	0	0
Верх.гр.	1	1	1	1
Цілочисел.	Ціле	Ціле	Ціле	ціле	ЦФ	напр
Коеж.в ЦФ	70	80	90	210	0	макс
		Обмеження
Вид					ліва част.	знак	Права част.
Трудові	10	15	22	28	0	<=	50
Фінанси	200	180	240	250	0	<=	650

Мал.2.

3. Ввести:

• адреса і напрямок функції мети: F7; Максимальне значення;

• Змінюючи комірки В3:Е3;

• Граничні умови:

B3 B4, C3 C4, D3 D4, E3 E4;

B3 B5, C3 C5, D3 D5, E3 E5; (2)

• Вимоги цілочисельності:

B3 –ціле; D3 – ціле;

C3 –ціле; E3 – ціле;

• Обмеження:

F10 H10, F11 H11.