Контрольні запитання

1. Для вирішення яких задач призначений метод динамічного програмування?

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

3. Які труднощі пов'язані з обчислювальними алгоритмами метод динамічного програмування?

4. Принципи динамічного програмування.

5. Принцип оптимальності Белмана.

6. Задача оптимальної заміни обладнання.

Література: [1 с. 195 – 212; 12 с.120 – 180; 24 с. 158 - 184]

Тема 7. Елементи теорії ігор

7.1. Концептуальні засади теоретико-ігрової моделі. Її основні компоненти.

7.2. Матричні ігри двох осіб. Платіжна матриця. Гра в чистих стратегіях. Мінімаксні стратегії. Сідлова точка. Змішані стратегії.

7.3. Основна теорема теорії ігор. Зведення задачі гри двох осіб до задачі лінійного програмування.

Контрольні запитання

1. Задачі і методи теорії ігор. Загальні свідомості. Економічні додатки.

2. Які критерії використовуються для визначення оптимальної стратегії?

3. Коли потрібна мінімаксна стратегія?

Література: [1 с. 213 – 222; 12 с. 446 – 515; 24 с. 185 - 196].

2. Порядок виконання контрольної роботи

Згідно вимогам учбового плану, після прослуховування теоретичного курсу студент виконує контрольну роботу.

Перед виконанням контрольної роботи необхідно освоїти теоретичний матеріал, використовуючи рекомендовану літературу.

Контрольна робота передбачає розв'язання 2-х задач. Номер варіанту визначається по номеру в журналі групи.

Номер варіанту обов'язково повинен бути наведений на першій сторінці контрольної роботи.

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

2.1. Вирішення задач лінійного програмування за допомогою функції «Поиск решения»

Тут розглядається сучасний підхід до викладу методів розв'язання задач математичного програмування за допомогою ЕОМ [25]. Цей алгоритм наочний, простий і надійний. Розглянемо його на декількох прикладах.

2.1.1. Приклад 1: структура виробництва

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

Таблиця 1.

Початкові дані для задачі оптимізації структури виробництва

Цех	Необхідний фонд робочого часу людино-годин на 1т			Обмеження по загальному фонду робочого часу, людино-годин на місяць
	“Доктор-ська”	“Москов-ська”	“Мислив-ська”
А. Виробництво	10	6	8	1300
Б. Внесення спецій	3	2	3	500
В. Упаковка	3	4	2	800
Прибуток грн. за 1 т	1500	900	1200	-

Позначимо через x_j — об'єм j-ой продукції, виробленої за місяць, т. Одержуємо математичний запис даної задачі:

Вводимо в Excel дані таблиці з початковими даними і складаємо другу таблицю із значеннями невідомих — об'ємів товарів, вироблюваних за місяць. Оскільки ці об'єми (х_j) ще не обчислені, приймаємо їх рівними 1.

Рис. 1. Початкова таблиця для оптимізації структури виробництва в Excel

Потім створюємо ще одну таблицю, де указуємо витрати і прибутки з розрахунку не на тонну, а на весь об'єм продукції. Заголовки рядків і стовпців такі ж, як і в першій таблиці, за винятком стовпця «Обмеження по загальній фундації робочого часу», яка замінюється стовпцем «Сума». Елементами таблиці є результати перемноження об'єму продукції одного вигляду на відповідні витрати робочого часу (в останньому рядку — на прибутки). В стовпець «Сумарні значення» заносимо суми по рядках.

Рис. 2. Обчислення витрат і прибутків на весь об'єм продукції

Заповнивши таблиці, вибираємо команду СервисПоиск решения. «Цільовою клітинкою» є E24 — останній клітинка стовпця «Сумарні значення». Інші елементи цього стовпця (витрати робочого часу) не повинні перевищувати відповідні елементи з першої таблиці (обмеження по загальній фундації робочого часу). Цю умову указуємо в «Обмеженнях». «Змінні значення» — це вміст другої таблиці. У вікні Параметры включаємо режим Неотрицательные значения. Оскільки вирішувана задача відноситься до лінійних, включаємо також режим Линейная модель.

Рис. 3. Пошук оптимального вирішення в Excel

Натиснувши кнопку Выполнить, одержуємо вирішення. Знайдені значення невідомих тепер знаходяться в другій таблиці, а третя таблиця містить докладний розрахунок витрат робочого часу і отриманих прибутків, відповідних знайденому розв'язанню.

Рис. 4. Результати розрахунку

Відповідь: треба виробляти тільки докторську ковбасу в обсязі 130 т/місяць, максимальний прибуток дорівнює 195 000 грн.