Дробово-лінійне програмування

Размещено на http://www.allbest.ru/

1. Економічна та математична постановка задач дробово-лінійного програмування

математичний програмування економічний виручка

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

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

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

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

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

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

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

Розв'язуючи економічні задачі, часто за критерій оптимальності беруть показники рентабельності, продуктивності праці тощо, які математично подаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так:

Z => max (min)

за умов

(i=1,n)

xj?0 (j=1,n)

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

Алгоритм розв'язування задачі дробово-лінійного програмування передбачає зведення її до задачі лінійного програмування. Щоб виконати таке зведення, позначимо:

=

зробимо заміну змінних

y_i= y₀x_j (j = 1,n)

і запишемо економіко-математичну модель:

max (min)

за умов

= 0 (i=1,n)

=1

y_j ?0 (j=1,n) y₀>0

2. Метод кусково-лінійної оптимізації задачі квадратичного програмування

Можна також за різними ознаками виокремити й підкласи. Це особливо стосується задач лінійного, нелінійного і стохастичного програмування. Наприклад, як окремий клас розглядають дробово-лінійне програмування, коли обмеження є лінійними, а цільова функція -- дробово-лінійна.

3. Графічним методом визначити оптимальний план задачі лінійного програмування

F = x1+x2 > min,

10x1+5x2?27

-5x1+3x2?17

x1+2x2?6

x1,x2?0

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

або

Межі області припустимих значень.

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

Розглянемо цільову функцію задачі F = x1+x2 > min. Побудуємо пряму, що відповідає значенню функції F = 0: F = x1+x2 = 0.Вектор-градієнт, що складений з коефіцієнтів цілющої функції, вказує напрямок мінімізації F(X). Початок вектору - точка (0;0), кінець (1;1).Будемо переміщувати цю пряму паралельно. Оскільки нас цікавить мінімальне рішення, переміщаємо пряму до першого торкання зазначеної області. На графіку ця пряма зазначена пунктирною лінією.

Пряма F(x) = const перетинає область в точці А. Так як точка А отримана в результаті перетину прямих 3 та 5, то ії координати задовольняють рівнянням цих прямих

x1+2x2=6

x1=0.

Вирішивши систему рівнянь, отримуємо x1 = 0, x2 = 3.

Звідси знайдемо мінімальне значення ці лівої функції:

F(X) = 1*0 + 1*3 = 3

4. Розв`язати задачу лінійного програмування симплекс-методом

max (2x₁ -x₂-3x₃)

2x₁+x₃?6

x₁ -x₂ - x₃= -2

x_j ?0, j=1,3

Розв`яжемо завдання з використанням симплексної таблиці.

Оскільки у правій частині присутнє мінусове значення, помножимо відповідні строчки на -1. Визначимо максимальне значення цільової функції F(X) = 2x₁ - 3x_{3 за} наступних умов обмежень:

2x₁ + x₃?6

- x₁ + x₂ + x₃=2.

Для побудови першого опорного плану систему не рівнянь приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми). В першому рівнянні вводимо базисну змінну х_4.

2x₁ + 0x₂ + 1x₃ + 1x₄ = 6

-1x₁ + 1x₂ + 1x₃ + 0x₄ = 2.

Введемо штучні змінні х : у першому рівнянні змінну х₂ визначемо як базисну:

2x₁ + 0x₂ + 1x₃ + 1x₄ = 6

-1x₁ + 1x₂ + 1x₃ + 0x₄ = 2.

Для встановлення задачі на максимум цільову функцію запишемо так:

F(X) = 2x₁-3x₃ > max.

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

Отриманий базис називається штучним, а метод рішення -методом штучного базису.

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

З рівнянь відображаємо штучні змінні, що підставимо у цільову функцію:

F(X) = 2x₁-3x₃ > max.

Матриця коефіцієнтів А= а_ij цієї системи рівнянь має вигляд:

A = 2 0 1 1

-1 1 1 0

5. Розв`язати транспортну задачу

а_i =(16,22;6) b_i = (10;16;18)

8 11 2

с_ij = 4 3 5

5 6 1

Відповідь:

F_x =2*16+4*6+3*16+5*4+1*2=126

Размещено на Allbest.ru