етап. Заповнення вікна Пошук рішення

РІШЕННЯ ЗАВДАНЬ ЛІНІЙНОГО ПРОГРАМУВАННЯ.

ОПТИМІЗАЦІЯ МЕТОДОМ ПОШУКУ РІШЕННЯ

Мета роботи:навчитися використовувати процесор Excel для вирішення задач оптимізації

1. Створення форми для введення умов завдання, введення в неї вихідних даних та залежностей із математичної моделі.

2.Введення даних із форми у вікно ExcelПошук рішенняз менюСервіс.

3. Завдання параметрів пошуку та розв'язання задачі.

Порядок виконання роботи:

1. Вивчити методичні вказівки.

2. Виконати завдання.

3. Оформити звіт та відповісти на контрольні питання.

МЕТОДИЧНІ ВКАЗІВКИ

Завдання лінійного програмування у випадку формулюється так:

Визначити максимум (мінімум) цільової функції F max(min) при заданій системі обмежень (2) та граничних умов (3):

Fmax(min) = A1 * X1 + A2 * X2 +. +An*Xn (1)

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

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

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

Обмеження—це умова, що накладається на деяку комірку. Обмеження можуть бути накладені на будь-які комірки таблиці, включаючи цільову комірку та комірки, що змінюються.

Щобзапуститипроцедуру пошуку рішення, треба:

1. У менюСервісвибрати командуПошук рішення. Відкриється діалогове вікноПошук рішення(Мал. 23).

2. У поліВстановити цільову коміркуввести посилання на комірку, в якій потрібно отримати максимальне, мінімальне або задане значення.

3. У поліЗмінюючи коміркиввести посилання на комірки, що змінюються. (Якщо клацнути по кнопці Припустити, то Пошук рішення самостійно визначить комірки, що змінюються).

4. Щоб задати обмеження, натисніть кнопкуДодати.

Рисунок 23 Діалогове вікно Пошук рішення

5. У діалоговому вікні, що відкрилося, слідує: (Мал. 24)

• у поліПосилання на коміркуввести посилання на комірку, що містить формулу, яка визначає обмеження; формула повинна прямо або опосередковано залежати від однієї або кількох змінних осередків;

• у другому полі вибрати оператор обмеження (>,

8. Змінювати та видаляти обмеження можна за допомогою кнопокЗмінититаВидалити.

9. За допомогою кнопкиПараметриможна встановити: максимальний час вирішення; гранична кількість ітерацій; відносну похибку; допустиме відхилення; збіжність; метод пошуку.

Якщо відомо, що задача, що розв'язується, лінійна (тобто залежності між змінними лінійні), то слід включити режимЛінійна модель: процес вирішення значно прискориться.

Для повернення в діалогове вікноПошук рішенняклацнути по кнопціОК.

10. Для ініціалізації процедури пошуку рішення клацнути по кнопціВиконати. Отримані результати буде виведено на робочий лист.

Після завершення процедури вирішення у діалоговомувікніРезультати пошуку рішенняможна виконати один із таких варіантів:

• зберегти знайдене рішення чи відновити вихідні значення робочому аркуші;

• зберегти параметри пошуку рішення як моделі;

• зберегти рішення у вигляді сценарію;

Поточні установки для пошуку рішення можна зберегти у вигляді моделі. Для цього треба в діалоговому вікніПараметри пошуку рішенняклацнути по кнопціЗберегти модельі вказати на робочому аркуші область для збереження моделі (можна вказати тільки верхню комірку області).

При збереженні моделі запам'ятовуютьсяцільова комірка, комірки, що змінюються, обмеження і параметри пошуку рішення.

Щоб згодом завантажити модель, потрібно натиснути кнопкуЗавантажити модельу діалоговому вікніПараметри пошуку рішення. (Діалогове вікно Параметри пошуку рішення відкривається при натисканні кнопкиПараметриу діалоговому вікні командиСервіс >• Пошук рішення).

Знайдені рішення (значення змінних осередків) можназберегти як сценарій.Для цього потрібно:

1. У діалоговому вікніРезультати пошуку рішеннявибратиЗберегти сценарій.

2. У поліНазва сценаріювведіть ім'я сценарію. Переглянути сценарії можна за допомогою командиСервіс > Сценарії.

За допомогою програмиПошук рішенняможна створити три типи звітів за результатами, отриманими при успішному завершенні процедури рішення.

Кожен звіт створюється на окремому аркуші поточної робочої книги.

Для створення звіту потрібно в діалоговому вікніРезультати пошуку рішеннявибрати потрібний тип звіту в поліТип звіту.Можна вибрати кілька типів (при виділенні кількох рядків використовується клавіша ).

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

•Стійкість—звіт містить відомості про ступінь залежності моделі від змін величин, що входять до формул, що застосовуються в задачі (формули моделі та формули обмежень).

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

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

Розглянемо застосування процесора Excel на вирішення ЗЛП з прикладу.

Завдання 1. МП випускає товари Х1, Х2, Х3, Х4, отримуючи від кожного прибуток в 60,70,120,130 крб. відповідно. Витрати виробництва наведено у таблиці.

1) Максимум прибутку залежно від оптимального розподілу витрат.

2)Минимум ресурсів, необхідні отримання максимальної прибыли.

Витрати	X1	X2	X3	X4	Усього
Трудові
Сировинні
Фінанси

Складемо математичну модель процесу з опису задачі:

60Х1+70Х2+120Х3+130Х4 = Fmax – цільова функція прибутку.

Розв'язання задачі засобами Excel складається з трьох етапів:

2. Введення даних із форми у вікно ExcelПошукрішенняз менюСервіс.

3. Завдання параметрів пошуку та розв'язання задачі.

Етап. Створення форми

а). Складання форми у вигляді:

A	B	C	D	E	F	G	H
Змінна	X1	X2	X3	X4	Формула	Знак	Св.член
Значення
Коеф. ЦФ	=СУМПРОВИЗВ (В$2:Е$2;В3:Е3)	max
Трудові	=СУМПРОВИЗВ (В$2:Е$2;В4:Е4)	=0, C2=0, D2=0 і Е2=0 для граничних умов Хi=0.

Також необхідно додати обмеження для отримання цілих величин за кількістю товарів:B2=ціл, C2=ціл, D2=ціл і Е2=ціл.

Після введення останньої граничної умови замість"Додати"натиснути клавішуОК, з'явиться вікно "Пошук рішення".

Для зміни або видалення обмежень та граничних умов використовуються клавішіЗмінити,Видалити.

Етап. Параметри пошуку.

У вікні "Пошук рішення" натиснути клавішу "Параметри", вибрати за промовчаннямМаксимальний час- 100 с.(можливо до 2^15=32767 c.> 4 год.),число ітерацій- 100 (для більшості завдань ця кількість прорахунків підходить з великим запасом), встановити прапорець у рядку "Лінійна модель", натиснутиОК, у вікні Пошук Рішення натиснутиВиконати(Рис. 25).

Рисунок 25 Діалогове вікно Параметри пошуку рішення

Результати пошуку рішення з таблицею результатів:

A	B	C	D	E	F	G	H
Змінна	X1	X2	X3	X4	Формула	Знак	Св.член
Значення
Коеф. ЦФ	max
Трудові

	наступна лекція = = gt;
Деякі алгоритми обробки масивів		Визначення середніх вмістів елементів у руді методом середнього арифметичного