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

Вступ

На практиці для випуску асортименту своєї продукції виробничі підприємства мають у своєму розпорядженні деякий запас, як правило, обмежених ресурсів (сировинних, трудових, енергетичних, паливних, грошових), деякий набір взаємозамінних технологій, устаткування і т.п. Транспортна фірма, що здійснює постачання від підприємств-виробників до замовників-споживачів, має можливість вибору в розподілі вантажу. Економіст або менеджер повинен скласти такий план випуску продукції, при якому досягається найкращий (оптимальний) результат: або підприємство максимізує прибуток, або максимізує випуск продукції, або мінімізує витрати на випуск продукції, або мінімізує виробничі відходи і т.п.

Методи розв’язування подібних завдань вивчаються студентами ВНЗ у дисципліні «Економіко-математичне моделювання», зокрема в її першій частині - математичному програмуванні. Найбільш поширеним є клас задач лінійного програмування (ЗЛП); розгляду методів розв’язання деяких із них присвячені дані методичні вказівки.

Спочатку вивчається графічний метод розв’язання ЗЛП, що дозволяє наочно представити як суть математичної постановки задачі, так і її результат. Потім вивчається розв’язання задачі з використанням убудованого в Microsoft EXCEL for WINDOWS інструмента «Поиск решения». Цей інструмент дозволяє розв’язувати більш складні задачі не тільки лінійного програмування. Традиційний симплексний метод розв’язання ЗЛП дозволяє одержати багато результатів, корисних для економічного аналізу рентабельності випуску окремих видів продукції, аналізу дефіцитності ресурсів, що використовуються, їхньої взаємозамінності. Однак цей метод досить трудомісткий. Вирішити цю проблему дозволяє Microsoft EXCEL із своєю вбудованою можливістю модифікації формул.

Також вивчається розв’язання транспортної задачі, модель якої лінійна, однак розв’язання цієї задачі симплексним методом є досить трудомістким. Для розв’язання цієї задачі розроблений зручний і наочний метод потенціалів, що став класичним. Крім цього методу, розглянуто розв’язок транспортної задачі з використанням інструмента «Поиск решения».

МЕТОДИ РОЗВ’ЯЗУВАННЯ ЗАДАЧ

ЛІНІЙНОГО ПРОГРАМУВАННЯ

ЗАВДАННЯ 1. Побудувати математичну модель економічної задачі. Розв’язати задачу за допомогою побудованої моделі

1. графічним методом,
2. з використанням інструмента “Поиск решения”,
3. симплексним методом.

Зробити висновки в термінах постановки задачі.

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

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

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

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

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

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

пар взуття – тижневий план випуску моделі №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 за тиждень.

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

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

1. комірки В2: D2 резервуємо для оптимальних значень змінних і (оптимального плану задачі), що будуть знайдені як результат застосування процедури «Поиск решения»;
2. комірку D3 резервуємо для значення цільової функції на оптимальному плані;
3. у комірки В3: D3 вносимо значення коефіцієнтів цільової функції;
4. комірки В5: С5, В6: С6, В7: С7 заповнюємо коефіцієнтами при змінних у лівій частині відповідних обмежень;
5. у комірки F5: F7 записуємо значення правих частин відповідних обмежень;
6. у комірки Е5: Е7 вносимо знак нерівності у відповідному обмеженні;
7. комірки D5: D7 резервуємо для значень лівих частин системи обмежень на оптимальному плані.

Внесемо формули, помітивши, що значення цільової функції (комірка D3) дорівнює сумі добутків невідомих значень змінних (комірки В2: С2) на коефіцієнти цільової функції (комірки В3: D3), а значення лівих частин системи обмежень (комірки 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 Екранна форма «Мастер функций»

1. серед вбудованих функцій цієї категорії відмітити
   «СУММПРОИЗВ» (рис. 1.3, б) і натиснути «ОК»;
2. в екранній формі (див. рис. 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 значення цільової функції на оптимальному плані, а в екранній формі, що з'явилися, «Результаты поиска решения», пропонується зробити один з видів звіту, з яких вибираємо звіт по стійкості і натискаємо «ОК». Аркуш «Отчет по устойчивости» представлений на рис. 1.12.

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

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