Розв’язання задачі цілочислового програмування засобами Excel

Розв’язання

Розв’язання задачі лінійного програмування засобами Excel

ПРИКЛАДИ ВИКОНАННЯ ЗАВДАНЬ ЗА ДОПОМОГОЮ ТАБЛИЧНОГО ПРОЦЕСОРУ EXCEL

Приклад. Знайти оптимальне рішення задачі лінійного програмування:

→ max

Введемо в клітинку А4 формулу цільової функцію в наступному вигляді: = 3*A1+5*A2+8*A3.

Значення в комірках А1, А2 і А3 відведемо під значення змінних , , відповідно. Числові значення змінних x1, x2 і x3 в ці комірки будуть введені автоматично в процесі виконання завдання.

У комірки В1, В2 і В3 введемо математичні формули обмежень у вигляді, зазначеному в таблиці 3.1.

Таблиця 3.1 – Математичні формули обмежень

Комірка	Математична формула
В1	= A1+5*A2+4*A3
В2	= A1+2*A2+A3
В3	= 5*A1+3*A2+4*A3

Потім введемо в комірку С1, С2 і С3 значення 315, 90 і 168 відповідного, що обмежують чисельні значення змінних завдання.

Для розв’язання цього завдання в Excel слід скористатися підпунктом Поиск решения пункту меню Сервис.

На екрані з'явиться таке вікно (рисунок 3.1):

Рисунок 3.1 – Вікно Поиск решения

У полі Установить целевую ячейку вказуємо клітинку А4. Розв’язання шукаємо для максимального значення, що зазначається перемикачем поля Равной, встановленим на записи зі словами максимальному значению.

У поле Изменяя ячейки вказуємо діапазон зміни комірки від А1 до А3, а саме $A$1: $A$3.

Після цього необхідно встановити обмеження, що враховуються при розв’язанні задачі. Для цього натискаємо на кнопку Добавить, розташовану праворуч від поля Ограничения. На екрані з’явиться наступне вікно (рисунок 3.2):

Рисунок 3.2 – Поле Добавление ограничения

Для додавання першого обмеження, а саме , у полі Ссылка на ячейку вказуємо комірку В1, потім у переліку, що розташований посередині, вибираємо знак "<=" і в полі Ограничение вказуємо комірку С1. Після цього натискаємо на кнопку Добавить. Аналогично додаємо решту обмежень задачі. Закриваємо вікно шляхом натискання кнопки Отмена.

Вікно Поиск решения набуде вигляду рисунок 3.3.

Рисунок 3.3 – Вікно Поиск решения

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

В Excel в якості методів пошуку рішення задачі пропонуються метод Ньютона і метод сполучених градієнтів. Для розв’язання завдань лінійного програмування звичайно використовується метод Ньютона. Граничне число ітерацій, відносна погрішність і допустиме відхилення вибираються відповідними тій задачі, оптимальне розв’язання якої знаходиться. Установки, що з’являються у вікні Параметры поиска решения (рисунок 3.4), зазвичай виявляються достатніми для отримання оптимального рішення задач лінійного програмування.

Рисунок 3.4 – Вікно Параметры поиска решения

У цьому вікні відзначаємо "галочкою" пункти Линейная модель і Неотрицательные значения. Натискаємо на кнопку "ОК", після чого знову

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

На екрані виводиться вікно Результаты поиска решения (рисунок 3.5).

Рисунок 3.5 – Вікно Результаты поиска решения

Натискаємо на кнопку "ОК".

Після цього в комірках, що були відведені для запису розв’язку задачі, з’являється числа (рисунок 3.6).

Рисунок 3.6 - Результат

У комірці А4 знаходимо значення цільової функції F (X), яке відповідає знайденому розв’язку. У комірках А1, А2 та А3 вказані відповідні значення змінних , , .

Для нашої задачі оптимальний розв’язок має вигляд:

, , , .

Задачі цілочислового програмування розв’язуються в Excel тими ж засобами, що й загальні завдання лінійного програмування. На відміну від завдань лінійного програмування, при розв’язанні завдань цілочислового програмування необхідно у вікні Добавление ограничения додати вказівку на те, що оптимальні значення змінних, які знаходяться, можуть приймати тільки цілі значення. Для цього у вікні Добавление ограничения потрібно вибрати в списку, розташованому посередині, значення "цел", як показано на рисунку 3.7.

Рисунок 3.7 – Цілочислова задача лінійного програмування

Дата добавления: 2017-02-01