МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Прізвище: Ім’я: Група: Кафедра: Дисципліна: Перевірив: Шагала Василь КНст-12 САПР Математичні методи Дослідження операцій [ім’я автора приховано] 
 Лабораторна робота №9 Розв’язання та аналіз задач булевого програмування за допомогою Excel Мета роботи: Вивчити метод розв’язання задач булевого програмування в Solver. Теоретичні відомості. 1.Рішення задач з булевими змінними. Частковим випадком задачі цілочисельних змінних являються задачі, в результаті рішення яких шукані зміні xj можуть приймати не любі цілі значення, а тільки одне з двох: або 0, або 1. Ці змінні, щоб їх відрізняти від звичайних, будемо позначати
j замість xj. Такі зміні на честь запропунувавшого їх англійського математика Джорджа Буля називаютьб булевими. Розповсюдженної задачею з булевими змінними являється задача вибору варіантів із числа заданих. Розглянемо таку задачу на прикладі. Є 4 варіанта використання ресурсів. Прибуток, який приносить кожний варіант, і ресурси як потребуються, таке і ті, якими володіють, приведені на мал.1. Варіанти  1  2  3  4 Наявність  Прибуток  70  80  90  210 --------  Трудові  10  15  22  28  50  Фінанси  200  180  240  250  650  Мал.1. Потрібно вибрати такі варіанти, щоб сумарний прибуток був максимальним. Приймаємо, що
Тоді математична модель задачі буде мати вигляд: F=70
1+80
2+90
3+210
4
max 10
1+15
2+22
3+28
4
50 200
1+180
2+240
3+250
4
650 (1) 0

j
1; j=

j- цілі. Подивимось, як вирішується така задача. Алгоритм. Рішення задачі з булевими змінними Для вводу умов задачі скласти форму і ввести початкові дані (мал.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. Виконання роботи. Варіанти індивідуальних завдань 17. 4x1 + 5x2 + 4x3 + 2x4 + x5  Max 2x1 + 4x2 + 3x3 + x4 + x5  8x1 + 6x2 + x3 + x4 + x5 14 Введеня обмежень для цільович функцій


Таблиця результатів  Змінні       ім'я x1 x2 x3 x4 x5    Значення 8 6 3 1 1    Нижн.гр. 2 4 3 1 1    Верх.гр. 8 6 1 1 1    Цілочисел. Ціле Ціле Ціле ціле ЦФ напр   Коеж.в ЦФ 128 272 281 282 283 макс     Обмеження       Вид     ліва част. знак Права част.  Трудові 2 4 3 1 1 <= 7  Фінанси 8 6 1 1 1 <= 14       0 0        0  0   Гістограма цілочисельних значень функцій Microsoft Excel 16.0 Отчет об устойчивости      Лист: [9.xlsx]Лист1        Отчет создан: 13.04.2016 16:33:34                           Ячейки переменных             Окончательное Приведенн. Целевая функция Допустимое Допустимое    Ячейка Имя Значение Стоимость Коэффициент Увеличение Уменьшение    $B$3 Значення x1 8 0 0 1E+30 0    $C$3 Значення x2 6 0 0 1E+30 0    $D$3 Значення x3 3 0 0 1E+30 0    $E$3 Значення x4 1 0 0 1E+30 0    $F$3 Значення x5 1 0 0 1E+30 0             Ограничения             Окончательное Тень Ограничение Допустимое Допустимое    Ячейка Имя Значение Цена Правая сторона Увеличение Уменьшение    $F$12 ліва част. 0 0 0 0 1E+30    $F$13 ліва част. 0 0 0 0 1E+30   
Звіти        Ячейка Имя Исходное значение Окончательное значение Целочисленное    $B$3 Значення x1 8 8 Продолжить    $C$3 Значення x2 6 6 Продолжить    $D$3 Значення x3 3 3 Продолжить    $E$3 Значення x4 1 1 Продолжить    $F$3 Значення x5 0 1 Продолжить                            Ячейка Имя Значение ячейки Формула Состояние Допуск   $F$12 ліва част. 0 $F$12=$G$12 Привязка 0   $F$13 ліва част. 0 $F$13>=$H$13 Привязка 0   $B$3 Значення x1 8 $B$3>=$B$4 Привязка 0   $B$3 Значення x1 8 $B$3>=$B$5 Привязка 0   $C$3 Значення x2 6 $C$3>=$C$4 Привязка 0   $C$3 Значення x2 6 $C$3>=$C$5 Привязка 0   $D$3 Значення x3 3 $D$3>=$D$4 Привязка 0   $D$3 Значення x3 3 $D$3>=$D$5 Привязка 0   $E$3 Значення x4 1 $E$3>=$E$4 Привязка 0   $E$3 Значення x4 1 $E$3>=$E$5 Привязка 0   $F$3 Значення x5 1 $F$3>=$F$4 Привязка 0   $F$3 Значення x5 1 $F$3>=$F$5 Привязка 0    Висновки: на даній роботі було проведено дослідження функцій булевого програмування в табличному процесорі за допомогою функції Solver/ Було проведено необхідні обчислення і отримані звіти та графіки.