Написание контрольных, курсовых, дипломных работ, выполнение задач, тестов, бизнес-планов
Новости все
Главная \ Методичні вказівки \ Методические указания и информация \ Цілочислове програмування

Цілочислове програмування

Дата публикации: 11.03.2019 08:58

Тема 5. Цілочислове програмування.

Мета: навчитися розв’язувати задачі цілочислового програмування засобами MS Excel

План.

1.  Вивчення алгоритму розв’язування задачі цілочислового програмування засобами MS Excel.

2. Розв'язування оптимізаційних задач з цілочисловими змінними на ПЕОМ

 

1.  Вивчення алгоритму розв’язування задачі цілочислового програмування засобами MS Excel.

Задача 1. Підприємство вирішило встановити додаткове устаткування, для розміщення якого виділено 19/3 м2 площі. На придбання обладнання підприємство має змогу витратити не більше 10 тис. грн. Комплект обладнання першого виду коштує 1 тис. грн., а другого – 3 тис. грн. Один комплект обладнання першого типу дозволяє збільшити випуск продукції за зміну на 2 од., а одного комплекту другого типу – на 4 од. При цьому один комплект обладнання першого типу потребує 2 м2 площі, а другого – 1 м2. Визначити такий набір додаткового обладнання, який дасть можливість максимально збільшити випуск продукції.

Розв’язок. Нехай х1 – кількість комплектів обладнання І виду, що придбає підприємство, а х2 – кількість комплектів обладнання ІІ виду Тоді змінні х1та х2 повинні задовольняти наступні нерівності:

                                                                                                                )

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

.                                                                                               

Згідно з економічним змістом змінні х1та х2  можуть приймати лише цілочислові невід’ємні значення:

,                                                                                                                          

- цілі числа.                                                                                                              

Алгоритм розв’язання цілочислових задач лінійного програмування засобами табличного процесору Excel:

  1. Вводять умову задачі:
    1. Створюють форму для введення умов задачі (рис. 1).

Примітка: під заголовком таблиці і перед колонкою «Тип обмеження» залишають відповідно порожній рядок і порожній стовпчик.

Рис. 1. Форма для введення умов задачі

 

  1. Вводять вхідні дані:
    1. Вводять залежності математичної моделі: у рядки обмежень заносять числові коефіцієнти при змінних, що відповідають назвам стовпчиків. Якщо деяка змінна в обмеженні відсутня, її стовпчик залишають пустим.
    2. Вводять коефіцієнти цільової функції (аналогічно у рядок F). Максимізація чи мінімізація функції позначається у цьому рядку у стовпчику «Тип обмеження».
    3. Вводять типи обмежень у стовпчик «Тип обмеження». Введення типу обмеження «=» повинно закінчуватись натисканням клавіші Enter.
    4. Вводять граничні умови, тобто праві частини обмежень у стовпчик «Розмір обмеження».
  1. Оформлюють умову задачі  у вигляді моделі.
    1. На перетині рядка, що відповідає і-му обмеженню, і пустого стовпчика вписують функцію =СУММПРОИЗВ (массив1; массив2), де массив1 – діапазон пустих клітинок під змінними ; массив2 – діапазон коефіцієнтів і-го обмеження.

Так, у нашому прикладі у клітинці Е4 запишеться функція

=СУММПРОИЗВ($C$3:$D$3;C4:D4).

Функція СУММПРОИЗВ використовується для обчислення суми добутків відповідних елементів числових масивів однакової розмірності. Синтаксис функції:

=СУММПРОИЗВ (массив1; массив2; масив3; ...)

де массив1, массив2, массив3,... - від 2 до 30 числових масивів.

Результат виконання даної функції – число, яке є сумою добутків відповідних елементів числових масивів.

Примітки:

  • масиви повинні мати однакові розмірності;
  • нечислові елементи масивів сприймаються як нульові.
  • Аналогічну функцію записують у рядок цільової функції.

 

2. Розв'язування оптимізаційних задач з цілочисловими змінними на ПЕОМ

Застосовують елемент надбудови табличного процесора Excel “Поиск решения”.

  1. Викликають пункти меню Сервис→Поиск решения. На екран виводиться діалогове вікно, зовнішній вигляд якого подано на рис. 2.

Рис. 2. Загальний вигляд вікна “Поиск решения”

 

  1. У полі “Установить целевую ячейку” вводять адресу клітинки, що містить формулу для обчислення значення цільової функції. Це можна зробити вручну (з клавіатури) або за допомогою кнопки , яка дозволяє перейти в робочу таблицю, і виділити потрібну клітинку. Повернення до вікна “Поиск решения” здійснюється за допомогою кнопки .

Примітка. Якщо перед викликом вікна “Поиск решения” курсор знаходився на клітинці, що містить формулу для обчислення значення цільової функції, то адреса цієї клітинки буде введена в поле “Установить целевую ячейку” автоматично.

У нашому прикладі адреса цільової клітинки Е7 встановлена автоматично.

  1.  Встановлюють перемикач “Равной” у положення, що відповідає спрямованості цільової функції (максимум, мінімум, деяке конкретне значення).

У нашому прикладі перемикач встановлено на “максимальному значению”.

  1. У полі “Изменяя ячейки” вводять адреси клітинок пустого рядка, що повинні містити значення змінних У нашому прикладі це клітинки $C$3:$D$3.
  2. Натискають кнопку “Добавить”. На екрані з’являється діалогове вікно “Добавление ограничения”, зовнішній вигляд якого подано на рис.3.

 

Рис. 3. Загальний вигляд вікна “Добавление ограничения”

 

  1.  Для кожного обмеження в поле “Ссылка на ячейку” вводять адресу клітинки, що містить значення функції СУММПРОИЗВ. У нашому прикладі для першого обмеження у полі “Ссылка на ячейку” введена адреса $E$4.
  2. Із списку, що розкривається, обирають тип обмеження.
  3. У полі “Ограничение” вводять адресу клітинки, що містить числове значення з колонки “Розмір обмеження” (рис. 4).

Рис. 4. Введення одного обмеження

 

Примітка. Для введення наступного обмеження натискають кнопку “Добавить”. Обмеження, що мають однаковий знак, можна вводити групами (рис. 5).

Рис. 5. Введення групи обмежень

 

В задачі цілочислового програмування обов’язковим є введення обмеження на те, що шукані змінні х1 та х2 – цілі числа. Для цього із спадного списку типу обмеження обирають рядок “цел”. Поле “Ограничение” залишити при цьому незаповненим.

 

Після введення останнього обмеження натискають кнопку “ОК”.

  1. У вікні “Поиск решения” натискають кнопку “Параметры” (рис. 6).

Рис. 6. Вікно “Параметры поиска решения”

  1. У вікні “Параметры поиска решения” встановлюють опції “Линейная модель”  і “Неотрицательные значения” і натискають кнопку “ОК”.
  2. У вікні “Поиск решения” (рис. 2) натискають кнопку “Выполнить”.

На екран виведеться вікно “Результаты поиска решения”, яке може містити такі повідомлення:

  1. “Решение найдено. Все ограничения и условия оптимальности выполнены”. Це означає, що знайдено оптимальний розв’язок моделі. Після натискання кнопки “ОК” на робочому листі у клітинці, що містила формулу для обчислення цільової функції, та під змінними  будуть виведені їхні значення.
  2. “Значение целевой ячейки не сходятся”. Це означає, що значення цільової функції прямує до нескінченості.
  3. “Поиск не может найти подходящего решения”. В даному випадку система обмежень несумісна і задача не має розв’язку.

 

Методичне забезпечення

  1. Сергієнко В.А. Математичне програмування. Конспект лекцій для студентів напряму підготовки 6.030601 „Менеджмент” денної та заочної форм навчання / В.А. Сергієнко, Л.П. Перхун, 2010. – 140 С.
  2. Лавров Є.А. Математичне програмування: навчальний посібник / Є.А. Лавров, Л.П. Перхун, В.А. Сергієнко / За ред. Є.А. Лаврова. – Суми, 2010. – 224 С.

 

Рекомендована література

Базова

  1. Бех О.Б. Збірник задач з математичного програмування. Навч. пос. / О.Б. Бех, Т.А. Огородня, А.Ф. Щебрак – К.: Видавництво Ліра-К, 2013. – 212 С.
  2. Бех О.Б. Математичне програмування. Пос. / О.Б. Бех, Т.А. Огородня, А.Ф. Щебрак – К.: Видавництво Ліра-К, 2013. – 200 С.
  3. Вдовин М. Л. Математичне програмування теорія та практикум. Пос. / М.Л. Вдовин, С.Г. Данилюк – К.: Видавництво Ліра-К, 2014. – 160 С.
  4. Глушик М. М. Математичне програмування. Підручник / М. М. Глушик, І.М. Копич, В.М. Сороківський – К.: Видавництво Ліра-К, 2014. – 280 С.
  5. Глушик М. Математичне програмування. Підручник / М. Глушик, І.Копич, О.Пенцак, В. Сорківський – К.: Видавництво Ліра-К, 2013. – 216 С.
  6. Копич І.М. Математичні моделі в менеджменті та маркетингу. Навч. пос. / І.М. Копич, В.М. Сороківський ,В.І.Стефаняк – К.: Видавництво Ліра-К, 2014. – 376 С.
  7. Кучма М.І. Математичне програмування: приклади та задачі. пос. / М.І. Кучма – К.: Видавництво Ліра-К, 2013. – 344 С.
  8. Мартиненко М.А. Математичне програмування: підручник / М.А. Мартиненко, О.М. Нещадим, В.М. Сафонов – К.: Видавництво Ліра-К, 2010. – 311 С.

 

Допоміжна

  1. Акулич И. Л. Математическое программирование в примерах и задачах. / И. Л. Акулич. – М: Высш. шк., 2008. – 450 с.
  2. Калетнік Г.М. Теоретичні основи моделювання та фінансово-економічні розрахунки в менеджменті / Г.М. Калетнік, С.В. Козловський, О.Г. Підвальна – К.: Видавництво Ліра-К, 2010. – 400 С.
  3. Толбатов Ю.А. Математичне програмування: підруч. для студ. вищ. навч. закл. / Ю.А. Толбатов, Є.Ю. Толбатов. - Т.: Підручники і посібники, 2008. – 432с.
  4. Уэйн Л. Винстон Microsoft Office Excel 2007. Анализ данных и бизнес моделирование. –М.: Издательство «Русская Редакция», 2008. – 608 с.
  5. Фортуна В.В. Основи економіко-математичного моделювання. пос. / В.В. Фортуна – К.: Видавництво Ліра-К, 2015. – 540 С.
  6. Хвищун І.О. Програмування і математичне моделювання: підручник для студ. вищих навч. закл. / І.О. Хвищун. – К.: Видавничий центр ЛНУ ім. Івана Франка, 2007. – 544c.

 

Інформаційні ресурси

(в т.ч. електронна бібліотека СНАУ)

  1. http://web.archive.org/web/20070205063920/http://dims.karelia.ru/~alexmou/tpr/tpr_02_linear_programming.ppt – слайди по лінійному програмуванню
  2. Український інститут ІТ в освіті Економіко-математичне моделювання (Демо-версія)  [Електронний ресурс]. – Режим доступу: http://moodle.ipo.kpi.ua/moodle/mod/resource/index.php?id=125
  3. Іващук О.Т. Економіко-математичне моделювання [Електронний ресурс] / О.Т. Іващук. – Т.: ТНЕУ «Економічна думка», 2008. – 704 с.
  4. Курило А.О. Математичне програмування. Конспект лекцій. - Суми, 2015 рік 136 ст., табл. 51, рис. 36.
  5. Курило А.О. Математичне програмування. Частина 1: методичні вказівки щодо виконання практичних та самостійних робіт. – Суми, 2015, ст.76, табл. 20, рис. 11.
  6. Курило А.О. Математичне програмування. Частина 2: методичні вказівки щодо виконання практичних та самостійних робіт. – Суми, 2015, ст.84, табл. 16, рис. 13.
  7. Сергієнко В.А.  Математичне програмування. Конспект лекцій для студентів напряму підготовки 6.030601 „Менеджмент” денної та заочної форм навчання./ В.А.Сергієнко, Л.П. Перхун. 2009 – 149 с.
  8. Сергієнко В.А., Перхун Л.П. Електронний засіб навчального призначення: «Математичне програмування» для студентів денної та заочної форм навчання за напрямом підготовки 6.030601 «Менеджмент», 2010.