русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Розв’язання задач лінійного програмування графічним методом


Дата додавання: 2014-11-27; переглядів: 1154.


 

Розберемо розв’язок однієї задачі оптимального виробничого планування (або задачі про використання ресурсів).

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

Ресурси Норми витрат ресурсів на один виріб Загальний запас ресурсів
№1 №2
Рабочий час (люд.-год) Шкіра I сорту (шмат.) Шкіра II сорту (шмат.) -
Прибуток (грн.)  

Скласти план випуску взуття в асортименті, що максимізує щотижневий прибуток.

Розв’язання. Спочатку складемо математичну модель поставленої задачі. Вона містить у собі змінні задачі, цільову функцію і систему обмежень.

Змінні задачі. Оскільки в задачі потрібно скласти тижневий план випуску взуття, то змінними задачі є:

пар взуття – тижневий план випуску моделі №1,

пар взуття – тижневий план випуску моделі №2.

Цільова функція задачі. Оскільки прибуток від випуску 1 пари взуття моделі №1 складає 50 грн., а моделі №2 – 70 грн., то загальний тижневий прибуток від випуску пар взуття моделі №1 і пар взуття моделі №2 складатиме (грн.). Таким чином, цільова функція задачі, яку необхідно максимізувати, має вигляд

.

Система обмежень задачі. З урахуванням наведених у таблиці даних можна скласти такі обмеження у вигляді нерівностей.

· Робочий час, затрачуваний на випуск запланованого взуття, складає (люд.-год.). З урахуванням загального фонду робочого часу в 900 люд.-год., який не можна перевищити, одержимо нерівність:

.

· Витрата шкіри I сорту (у шматках) на виготовлення запланованої партії взуття представиться за аналогією з попередньою нерівністю:

.

· Витрата шкіри II сорту (у шматках) – відповідно:

.

Якщо обидві частини останньої нерівності поділити на 3, то одержимо:

.

· План випуску взуття за смислом не може набувати від’ємних значень, тому останнє обмеження невід’ємності змінних:

.

Таким чином, математична модель задачі має вигляд:

пар взуття – тижневий план випуску моделі №1,

пар взуття – тижневий план випуску моделі №2,

Математична модель виражається через дві змінні, тому для розв’язання задачі можна застосовувати графічний метод.

На координатній площині зобразимо множину точок , координати яких задовольняють системі обмежень. Ця множина називається областю припустимих розв’язків (областю припустимих значень).

Спочатку зауважимо, що система обмежень містить нерівності , які означають, що шукана область лежить у першій чверті. Далі побудуємо прямі

, (1)

, (2)

. (3)

Для цього знайдемо по дві пари точок, через які проходить кожна з цих прямих:

1. : (0, 450), (900, 0);

2. : (0, 900), (300, 0);

3. : (0, 400), (500, 400).

Ці прямі з відповідними мітками зображені на рис. 1.1.

Множина точок, які задовольняють нерівності , являє собою півплощину, що обмежена прямою . Оскільки точка О(0,0) задовольняє нерівності ( - вірно), то шукана півплощина містить цю точку; це зображено на рис. 1.1 за допомогою стрілок. Аналогічно, точка О(0,0) задовольняє кожній із нерівностей і , тому ця точка міститься у відповідних півплощинах (див. рис. 1.1). З урахуванням розташування в першій чверті область припустимих розв’язків являє собою заштрихований многокутник OABCD.

Рис. 1.1 – Розв’язання задачі лінійного програмування графічним методом

 

Тепер зобразимо вектор найшвидшого росту цільової функції , яким є вектор, співспрямований її градієнту. Координатами вектора градієнта (для лінійної відносно змінних функції) є коефіцієнти при змінних цільової функції, тобто . Як вектор оберемо для зручності побудови вектор

.

Для зображення цього вектора з'єднуємо спрямованим відрізком точки з координатами (0, 0) і (500, 700). Довільна лінія рівня цільової функції (L) проходить перпендикулярно до вектора .

Для пошуку точки області припустимих розв’язків, у якій цільова функція досягає свого максимуму (мінімуму), необхідно лінію рівня пересувати в напрямку вектора градієнта (відповідно у зворотному напрямку). Крайня точка області при такому русі буде відповідати оптимальному розв’язку. У даній задачі такою точкою буде точка С. Знайдемо її координати, зауваживши, що вона є точкою перетинання прямих (1) і (2). Тому розв’яжемо систему

.

Із першого рівняння виразимо :

. (4)

Потім підставимо знайдений вираз у друге рівняння:

,

звідки одержимо

Знаючи , за допомогою (4) знаходимо :

.

У результаті дійдемо висновку, що , а точка, яка відповідає оптимальному розв’язку, має координати . Максимальне значення цільової функції:

(грн.).

Відповідь. Для одержання максимального тижневого прибутку, що складає 34200 грн., фабрика повинна випускати 180 пар взуття моделі №1 і 360 пар взуття моделі №2 за тиждень.

 

2 Розв’язання задач лінійного програмування за допомогою інструмента “Поиск решения”

 

Відповідно до математичної моделі поставленої задачі підготуємо аркуш EXCEL для застосування інструмента «Поиск решения» (див. рис. 1.2):

1) комірки В2:C2 резервуємо для оптимальних значень змінних і (оптимального плану задачі), що будуть знайдені як результат застосування процедури «Поиск решения»;

2) комірку D3 резервуємо для значення цільової функції на оптимальному плані;

3) у комірки В3:C3 вносимо значення коефіцієнтів цільової функції;

4) комірки В5:С5, В6:С6, В7:С7 заповнюємо коефіцієнтами при змінних у лівій частині відповідних обмежень;

5) у комірки F5:F7 записуємо значення правих частин відповідних обмежень;

6) у комірки Е5:Е7 вносимо знак нерівності у відповідному обмеженні;

7) комірки D5:D7 резервуємо для значень лівих частин системи обмежень на оптимальному плані.

Внесемо формули, помітивши, що значення цільової функції (комірка D3) дорівнює сумі добутків[1] невідомих значень змінних (комірки В2:С2) на коефіцієнти цільової функції (комірки В3:C3), а значення лівих частин системи обмежень (комірки D5, D6 і D7) дорівнюють сумі добутків невідомих значень змінних (комірки В2:С2) на коефіцієнти лівих частин системи обмежень (комірки В5:С5, В6:С6, В7:С7 відповідно). Для цього в цільову комірку D3 вносимо формулу

СУММПРОИЗВ($B$2;$C$2;B3;C3),

яку копіюємо в комірки D5, D6 і D7 з модифікаціями.

Для внесення в комірку D3 зазначених формул необхідно

1) поставити курсор у комірку D3;

2) викликати “Мастер функций” за допомогою кнопки (див. рис. 1.2);

3) серед категорій майстра функцій вибрати «Математические» (рис. 1.3, а);

а) б)
Рис. 1.3 ‑ Екранна форма «Мастер функций»

4) серед вбудованих функцій цієї категорії відмітити
«СУММПРОИЗВ» (рис. 1.3, б) і натиснути «ОК»;

5) в екранній формі (див. рис. 1.4), що з'явилася, поставити курсор у «Массив 1», виділити на аркуші EXEL комірки В2:C2 (відповідають зарезервованим значенням змінних), потім привласнити їм абсолютні адреси натисканням функціональної клавіші F4; перевести курсор у «Массив 2» і виділити на аркуші EXEL комірки В3:С3 (відповідають значенням коефіцієнтів цільової функції).

Рис. 1.4 ‑ Програмування цільової комірки

Після копіювання формул у комірки D5, D6 і D7 вони будуть модифіковані так, як показано на рис. 1.5.

Рис. 1.5 ‑ Програмування комірок, що відповідають значенню цільової функції і значенням лівих частин системи обмежень

Якщо перелік процедур «Сервис» у меню Microsoft EXEL не містить інструмент «Поиск решения», то для додавання цього інструмента в перелік необхідно виконати такі дії:

1) натиснути «Сервис», потім «Надстройки» (рис. 1.6 а);

2) в екранній формі, що з'явилася, відмітити «Поиск решения» (рис. 1.6, б).

а) б) Рис. 1.6 ‑ Додавання процедури «Поиск решения» в меню «Сервис» Microsoft EXEL

У результаті пророблених операцій аркуш EXEL готовий для запуску процедури «Поиск решения». Вибираємо в “Сервис” процедуру “Поиск решения” (див. рис. 1.7).

Рис. 1.7 ‑ Запуск процедури «Поиск решения»

В екранній формі «Поиск решения» (див. рис 1.8)

1) установлюємо цільову комірку $D$3, відзначаючи її на аркуші EXEL;

2) відзначаємо прапорцем тип оптимізації, виходячи з умов задачі: у даному випадку – це максимізація;

3) переводимо курсор в «Изменяя ячейки» і виділяємо на аркуші EXEL комірки $В$2:$С$2, що відповідають зарезервованим значенням змінних;

4) переводимо курсор в «Ограничения», натискаємо «Добавить»;

Рис. 1.8 ‑ Екранна форма «Поиск решения»  
Рис. 1.9 ‑ Екранна форма «Добавление ограничений»  
Рис. 1.10 ‑ Екранна форма «Параментры поиска решений»

5) в екранній формі «Добавление ограничений» (рис. 1.9)

а) робимо посилання на комірки (шляхом їхнього виділення на аркуші EXEL), що відповідають лівим частинам системи обмежень $D$5:$D$7; ці комірки містять результат обчислень відповідно до введених раніше формул;

б) установлюємо знак, що відповідає знаку нерівності системи обмежень: у даному випадку це «<=»; якщо не всі обмеження мають однаковий знак, то, розташувавши поруч нерівності одного знака, програмують окремо кожну з груп, що утворилися;

в) переводимо курсор в «Ограничения», посилаючись на комірки, що відповідають правим частинам системи обмежень $F$5:$F$7, виділяючи їх на аркуші EXEL;

г) натискання «ОК» повертає нас в екранну форму «Поиск решения»;

6) натискаємо «Параметри», в екранній формі, що з'явилася, (рис. 1.10) відмічаємо прапорцями «Линейная модель» і «Неотрицательные значения», після чого натискання «ОК» повертає нас до екранної форми «Поиск решения»;

7) натискаємо «Выполнить», у результаті чого (рис. 1.11) на аркуші EXEL у комірках В2:С2 висвічуються шукані значення оптимальних змінних (оптимальний план), у комірці D3 ‑ значення цільової функції на оптимальному плані, а в екранній формі, що з'явилися, «Результаты поиска решения», пропонується зробити один з видів звіту, з яких вибираємо звіт по стійкості[2] і натискаємо «ОК». Аркуш «Отчет по устойчивости» представлений на рис. 1.12.

Рис. 1.11 ‑ Результати роботи процедури «Поиск решения»

 

Рис. 1.12 ‑ Екранна форма аркуша «Отчет по устойчивости»

 


<== попередня лекція | наступна лекція ==>
Лабораторна робота | Розв’язання задач лінійного програмування симплексним методом


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн