< Попер   ЗМІСТ   Наст >

Задачі лінійного програмування та їх застосування

Загальна постановка

Завдання МП, в якій всі функції, що входять в модель мають лінійний вигляд, а додаткові вимоги полягають у невід'ємності компонент вектора . Задача ЛП зазвичай записується в скороченому вигляді і представляється так

при обмеженнях

– де в будь-якому обмеженні має будь-який знак відношення, тобто .

Кожна задача лінійного програмування має в собі сполучену задачу, звану двоїстою. Вихідна і їй двоїста задачі становлять двоїсту пару задач ЛП. Двоїста задача використовується для дослідження рішення вихідної задачі. Вона формулюється після того, як побудована математична модель вихідної задачі. Формування моделі двоїстої задачі здійснюється відповідно до певних правил на основі тих же самих вихідних даних. Симетрична двоїста пара складається з двох стандартних моделей задач ЛП.

Вихідна задача ЛП записана в стандартній формі така:

при обмеженнях

Їй двоїста буде наступна

при обмеженнях

Виходячи з двоїстої пари задач ЛП, можна зробити наступні твердження [ ]:

– якщо, де. – оптимальний план вихідної задачі, а– їй двоїста, то- оптимальні значення цільових функцій

збігаються;

  • – якщо, то - обмеження є вузьким методом в системі обмежень;
  • – якщо• то
  • – якщо , то, то
  • – якщо збільшити на одиницю, то збільшиться на величину

Таким чином, вирішивши двоїсту задачу, ми отримаємо наступну інформацію про вихідну задачу:

  • – структуру оптимального плану;
  • – оптимальне значення цільової функції;
  • – вузькі місця в системі обмежень;
  • – на скільки зміниться оптимальне значення цільової функції, якщо збільшимо на одиницю компоненту в обмеженні, що є вузьким місцем.

Задача та математична модель визначення оптимальної виробничої програми підприємства (ВОВПП)

Постановка задачі. Підприємство може випускати найменувань виробів. Для цього використовується видів ресурсів, наявних в обсязі кожного. Відома норма витрати кожного виду ресурсу на виготовлення одиниці кожного найменування виробів. Позначимо через . Відомо також, який прибуток отримає підприємство, якщо реалізує одиницю продукції. Позначимо через cj (/ = 1,я). Необхідно визначити обсяг випущеної продукції кожного найменування, щоб, витрачаючи тільки наявні ресурси, отримати максимальну кількість прибутку.

Математична модель формується так:

  • – мета моделювання – максимальна кількість прибутку 2;
  • – шукані величини – обсяг випуску продукції кожного найменування -;
  • – запис цільової функції через шукані величини

– запис системи обмежень через шукані величини

Класична вимога до шуканих величин, що означає обсяг випуску продукції

Отримана модель відповідає моделі ЛП, записаної в стандартному вигляді, їй двоїста задача представляється моделлю

при обмеженнях

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

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

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

Таким чином, двоїста задача до задачі ВОВПП говорить: які ціни слід призначити на ресурси, щоб сумарна вартість всіх наявних ресурсів була б мінімальною і при цьому, щоб витрати всіх ресурсів на одиницю найменування виробу були б порівнянні з величиною прибутку від цієї одиниці.

Нехай визначені оптимальні облікові ціни ресурсів . З задачі ВОВПП знаємо максимальну величину прибутку

асортимент продукції, що випускається

випливає, що , тобто вироби випускаються в обсязі xj

дефіцитні ресурси

випливає, що , тобто весь ресурс витрачається повністю.

Можемо також подивитися, вигідно чи ні збільшувати кількість дефіцитного ресурсу. Якщо - дефіцитний ресурс, - ціна одиниці цього ресурсу, то якщо , то вигідно. Інакше це робити не має сенсу.

Приклад.

Підприємство випускає вироби А і В. Для їх виготовлення необхідно чотири види ресурсів, запаси яких обмежені: 5700 верстатогодин роботи токарних верстатів; 3300 – фрезерних; 5000 – верстатогодин слюсарно-складальних робіт та 610 кілограмів напівфабрикатів.

Для виготовлення одного виробу типу А необхідно верстатогодин: 300 токарних, 200 фрезерних, 200 слюсарно-складальних робіт і 10 кг. напівфабрикатів.

Для виготовлення одного виробу типу В необхідно верстатогодин: 400 токарних, 100 фрезерних, 500 слюсарно-складальних робіт та 70 кг. напівфабрикатів.

Мінімальна кількість виробів типу А, які повинні бути виготовлені становить 10 одиниць, випуск виробів типу В не лімітований. Прибуток від реалізації виробу типу А становить 3 тис. грн., А типу В – 8 тис. грн.

Необхідно визначити такий план випуску виробів А і В, при якому сумарна величина прибутку від реалізації, була б максимальною.

Нехайтапредставляють обсяг випуску продукції А і В відповідно. Математична модель буде мати вигляд

при обмеженнях

Оптимальний план випуску виробів наступний: тис. грн. Крім того, залишилися запаси ресурсів: 300 верстатогодин токарних робіт, 700 верстатогодин фрезерних робіт, слюсарно-складальні роботи вичерпалися повністю, напівфабрикатів залишилося 90 кг.

Двоїста задача запишеться так

при обмеженнях

Рішення двоїстої задачі наступне ,тис. грн. Час роботи токарних , фрезерних верстатів і напівфабрикатівмається в залишку. Слюсарно-складальні роботи дефіцитні . Жорстким обмеженням є і обмеження на кількість виробів типу А.

Значення показує, що якщо дефіцитні слюсарно- складальні роботи збільшити на одну верстатогодину, то величина прибутку збільшиться на 0,016 тис. грн. Значення показує, що зменшення жорсткості на випуск виробів типу А з 10 до 9 призведе до збільшення прибутку на 0,2 тис. грн. Обмеження на кількість виробів типу А більше важливе, ніж обмеження на дефіцитний ресурс по слюсарно-складальним роботам.

 
< Попер   ЗМІСТ   Наст >