Розв’язання задач лінійного програмування (стр. 4 из 5)

Кожна одиниця інформації (ім'я, адреса, число продажів в місяць і ін.) займає свою власну клітинку в створюваній робочій таблиці. У кожній робочій таблиці 256 стовпців (з яких в новій робочій таблиці на екрані видно, як правило, тільки перші 10 або 11 (від А до J) і 65 536 рядків (з яких зазвичай видні тільки перші 15-20). Кожна нова робоча книга містить три чистих листа робочої таблиці.

Вся інформація, що поміщається в електронну таблицю, зберігається в окремих клітинках робочої таблиці. Але ввести інформацію можна тільки в поточну клітинку. За допомогою адреси в рядку формул і табличний курсор Excel вказує, який з 16 мільйонів клітинок робочої таблиці є поточним.

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

Тому можна зробити висновок, що даний програмний пакет найкраще підходить для розв’язку задач лінійного програмування.

4.3 Опис вхідних та вихідних даних

Дана програма написана в Excel. В ній задаються обмеження і значення цільової функції, які можна змінювати. Потім програма проводить розрахунки і в клітинках, яким попередньо були присвоєнні спеціальні імена, записує розв’язок функції мети і значення змінних, при яких цей оптимальний розв’язок був отриманий. Розглянемо всі введення даних детальніше.

Вхідними даними для даної задачі є виражені з обмежень значення кожної змінної

та вираз для обчислення цільової функції. Значення змінних вводяться в поле «Ограничения» в меню інструменту Пошук розв'язку. Вираз значення цільової функції вводиться в комірку робочого аркуша.

Вихідними даними є значення кожної змінної

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

4.4 Розробка структури програми

Щоб отримати розв'язок задачі лінійного програмування за допомогою Excel потрібно виконати наступні дії:

1. В заданій задачі три змінних, тому клітинкам

потрібно присвоїти імена відповідно - витрати на рекламу по телебаченню; - витрати на радіорекламу; - витрати на рекламу у газетах. Для цього викликаємо команду Вставка → Имя → Присвоить. У вікні, що появилося записуємо ім’я, яке хочемо присвоїти клітинці, для першої клітинки це буде , і натиснути Enter. Для двох решти клітинок, що залишилися виконуємо аналогічні дії у присвоєнні імені. Після цього у клітинці аналогічно, як і для змінних, присвоюємо ім’я , в ній програма запише розв’язок даної задачі (рисунок 4.4.1):

Рисунок 4.4.1 – Вікно для присвоєння імені для комірки цільової функції

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

3. Запускаємо програму. Спочатку натискаємо на вкладку Сервис, що знаходиться на панелі інструментів, і в меню, що появилося, вибираємо Поиск решения (рисунок 4.4.2):

Рисунок 4.4.2 – Заповнення вікна Поиск решения

В даному діалоговому вікні встановлюємо значення цільової клітинки

та зазначаємо пошук максимуму цільової функції. Задаємо клітинки, в яких буде розв'язок даної задачі — діапазон клітинок від до . За допомогою кнопки Добавить додаємо обмеження у вигляді восьми обмежень (рисунок 4.4.3):

Рисунок 4.4.3 – Вікно для додавання обмежень

В меню Параметры відмічаємо, що модель лінійна (рисунок 4.4.4):

Рисунок 4.4.4 – Вікно для визначення параметрів

Натиснувши на кнопку Вьполнить отримуємо розв'язок задачі (рисунок 4.4.5):

Рисунок 4.4.5 – Розв’язок даної задачі

В комірках

отримали відповідні значення , а в комірці максимальне значення цільової функції.

4.5 Розробка схеми алгоритму

На рисунку 4.5.1 приведена схема алгоритму програми:

Рисунок 4.5.1 – Схема алгоритму програми

4.6 Розробка тестів

У якості тесту будемо використовувати розв'язок задачі, отриманий вручну. Для цього отриману у третьому розділі даної роботи модель заносимо до симплекс таблиці (таблиця 4.6.1):

Таблиця 4.6.1 – Ітерація 1

	1	1	1	1	0	0	10000
	1	1	0	0	1	0	6000
	0	2	-1	0	0	1	0
	20	8	12	0	0	0	0

Знаходимо базисний елемент: шукаємо стовпчик з максимальним коефіцієнтом

і рядок з мінімальним відношенням / .

Отриманий елемент є базисним елементом. Тепер змінну

виводимо з базису, а вводимо в базис. Кожний елемент вибраного рядка ділимо на базисний елемент і перераховуємо таблицю за правилом прямокутника.

Елементи

перераховуємо за коефіцієнтами. Отримуємо симплекс-таблицю 4.6.2.

Таблиця 4.6.2 – Ітерація 2

	0	0	1	1	-1	0	4000
	1	1	0	0	1	0	6000
	0	2	-1	0	0	1	0
	0	-12	12	0	-20	0	-120000

Перевіряємо елементи рядка

. Оскільки вони всі не від’ємні і не нульові, продовжуємо розрахунок далі. Отримуємо базисний елемент. Перераховуємо таблицю, як було показано раніше. Отримуємо симплекс-таблицю 4.6.3.