Теоретичні відомості

Розглянемо постановку задачі на прикладі. Нехай цех підприємства випускає два види продукції (Продукт 1 і Продукт 2). Необхідно розрахувати оптимальні тижневі обсяги (х1, х2) випуску цих продуктів з точки зору максимізації прибутку. Прибуток за робочий тиждень (цільова функція - F) від першого продукту складає 5 одиниць, від другого – 5,5. На виробництві діють обмеження по сировині, трудовим ресурсам та транспортним витратам:

1. Для Продукту 1 потрібно 3 одиниці сировини, для Продукту 2 – 6 одиниць сировини. Всього цех має 18 одиниць сировини.

2. Для виготовлення Продукту 1 потрібно 6 робітників, для Продукту 2 – 4. В цеху працює всього 24 робітника.

3. Транспортні витрати на перевезення Продукту 1 складають 2 одиниці, Продукту 2 – 1 одиницю. Ці витрати не можуть бути меншими за 2 одиниці (в ці одиниці входять витрати на оренду одного автомобіля мінімальної вантажопідйомності протягом одного дня). Вважаємо, що вся денна продукція цеху може бути вивезена на одному вантажному автомобілі.

Окрім того очевидно, що жодна з величин, що розглядаються, не може бути меншою за нуль. Маючи такі початкові дані запишемо співвідношення, з яких можна обрахувати оптимальні обсяги виробництва Продукту 1 та Продукту 2. Позначимо види продукції як Х₁ та Х₂ відповідно. Розв’язком такого роду задач займається розділ математики, що називається математичним програмуванням. Але системи, що містять в собі не більше двох змінних можуть бути також розв’язані графічно. Для порівняння розв’яжемо дану задачу двома способами графічно і за допомогою засобів програми MS Excel. Умови, задачі можна записати у вигляді наступних співвідношень:

Графічний розв’язок зводиться до наступного:

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

2. Розв’язок шукається в напівплощині, всі точки якої задовольняють нерівності.

3. Щоб визначити цю напівплощину необхідно послідовно прирівняти до нуля значення Х₁ та Х₂.

4. Побудова даних прямих представлена на рисунку. Штриховка біля обмежуючих прямих направлена в сторону області розв’язків.

Після того як побудовано графічний розв’язок системи, може бути визначена область, що задовольняє всім обмеженням (багатокутник розв’язків). В нашому випадку дана область - це багатокутник, вершини якого позначені на рисунку чорними і білими кільцями. Відомо, що оптимальний розв’язок обов’язково знаходиться на межі цієї області, зазвичай в одній із її вершин. Пряма цільової функції зображена на рисунку жирною пунктирною лінією. Початково вона проводиться довільно відносно області розв’язків: на графіку – через точки Х₁=5,5 і Х₂=5. Оскільки у цільової функції відсутня права частина, ми можемо однозначно визначити тільки нахил прямої по реперним точкам Х₁=5,5 і Х₂=5. Для знаходження максимально можливого допустимого значення цільової функції її необхідно переміщувати паралельно самій собі до перетину з точкою на границі багатокутника розв’язків, де її значення максимальне. Як видно з рисунка - це точка перетину прямих 1 та 2. Щоб знайти її координати та значення цільової функції необхідно розв’язати спільно рівняння 1 та 2.

В результаті отримаємо Х₁=3 і Х₂=1,5. Це і є оптимальний розв’язок. При цьому прибуток цеху буде дорівнювати F=5*3+5,5*1,5=23,25. Переміщуючи пряму цільової функції, також можна знайти і мінімальне значення. Це точка, де Х₁=1 і Х₂=0. В цьому випадку цільова функція буде дорівнювати F=5*1+5,5*0=5. Тут виникає цілком природне питання – чому мінімальне значення прибутку 5, а не нуль (тобто повне звертання виробництва). Справа в тому, що умови нашої задачі визначають обов’язкові транспортні витрати не менше, ніж 2 одиниці, оскільки за договором оренди автомобіль орендується в будь-якому випадку.

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

Для застосування Поиск решения необхідно:

1. Детально ознайомитися з умовами та обмеженнями задачі оптимізація яку необхідно розв’язати.

2. Скласти систему нерівностей.

3. Створити таблицю з початковими даними, причому у вигляді зрозумілому для читання, так як це, наприклад, виконано в таблиці наведеній нижче. Колонка “Обмеження” заповнюється у відповідності до складених нерівностей. Значення Х₁ та Х₂ на початковому етапі беруться довільно, але при цьому обов’язково повинні виконуватися всі нерівності, наприклад Х₁=1 та Х₂=1. Значення полів “Продукт 1” та “Продукт 2” заповнюються у відповідності до умов задачі. Поля “Розрахункові значення” та “Прибуток” розраховуються за формулами, представленими в системі нерівностей, при цьому використовуються довільно задані значення Х₁ та Х₂.

4. Виділити комірку зі значенням поля “Прибуток” і виконати команду Данные, Анализ: Поиск решения.

5. В діалоговому вікні, що з¢явиться, ввести всі обмеження та задати адреси комірок, які можна змінювати в процесі генерації оптимального розв’язку та адресу цільової комірки, в якій розраховується максимальний прибуток.

6. В результаті виконання процедури Поиск решения отримаємо таблицю з розв’язками.

Як видно з таблиці значення прибутку (цільової функції) та обсяги виробництва Продукту 1 та Продукту 2 співпадають з результатами, що були отримані графічним методом. Також можна порівняти граничні та фактично необхідні значення ресурсів.