44.Метод штучного базису

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

Розглянемо задачу лінійного програмування:

(1)

(2) (3)

Задача подана в канонічному вигляді і система обмежень (2) не містить одиничної матриці. Отримати одиничну матрицю можна, якщо до кожного рівняння в системі обмежень задачі додати одну змінну . Такі змінні називають штуч­ними. (Не обов’язково кількість введених штучних змінних має дорівнювати m. Їх необхідно вводити лише в ті рівняння системи обмежень, які не розв’язані відносно базисних змінних.) Допустимо, що система рівнянь (2) не містить жодного одиничного вектора, тоді штучну змінну вводять у кожне рівняння:

(4)

У результаті додавання змінних у рівняння системи (2) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (4) називають розширеною, або М-задачею. Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві. Тоді система обмежень (4) набуде вигляду (2) (не міститиме штучних змінних), а розв’язок розширеної задачі буде розв’язком і задачі 1-3

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

(У разі розв’язання задачі на відшукання мінімального значення цільової функції вводять коефіцієнти, які є досить великими числами. Цільова функція тоді має вигляд: ).

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

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

Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му — ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком.

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

Теорема Якщо в оптимальному плані розширеної задачі штучні змінні , то план є оптимальним планом початкової задачі.

№ 45 Нелінійні оптимізаційні моделі. Загальний запис математичної моделі. Функція Лагранжа

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

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

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

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

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

(8.1)

за умов:

( ); (8.2)

. (8.3)

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

Функція Лагранжа

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

Розглянемо метод множників Лагранжа для розв’язування задачі нелінійного програмування, що має вигляд:

(8.6)

за умов:

, (8.7)

де функції і мають бути диференційовними.

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

Переходимо до задачі пошуку безумовного екстремуму. В літературі [13, 28] теоретично доведено, що постановки та розв’язання таких задач еквівалентні.

Замінюємо цільову функцію (8.6) на складнішу. Ця функція називається функцією Лагранжа і має такий вигляд:

де — деякі невідомі величини, що називаються множниками Лагранжа.

№ 46 Теорія двоїстості в лінійних оптимізаційних задачах. Математична модель прямої та двоїстої задач. Загальний запис моделей.

Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.

Економічну інтерпретацію кожної з пари таких задач розглянемо на прикладі виробничої задачі (§ 2.1).

Пряма задача: max F = c1x1 + c2x2 + … + cnxn (3.1)

за умов: (3.2)

. (3.3)

Необхідно визначити, яку кількість продукції кожного j-го виду необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: наявні обсяги ресурсів — ; норми витрат і-го виду ресурсу на виробництво одиниці j-го виду продукції — , а також — ціни реалізації одиниці j-ої продукції.

Розглянемо тепер цю саму задачу з іншого погляду. Допустимо, що за певних умов доцільно продавати деяку частину чи всі наявні ресурси. Необхідно визначити ціни ресурсів. Кожному ресурсу поставимо у відповідність його оцінку . Умов­но вважатимемо, що — ціна одиниці і-го ресурсу.

На виготовлення одиниці j-го виду продукції витрачається згід­но з моделлю (3.1)—(3.3) m видів ресурсів у кількості відповідно . Оскільки ціна одиниці і-го виду ресурсу дорівнює , то загальна вартість ресурсів, що витрачаються на виробництво одиниці j-го виду продукції, обчислюється у такий спосіб:

.

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

.

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

.

Отже, в результаті маємо двоїсту задачу:

(3.4)

за умов: (3.5)

(3.6)

Задача (3.4)—(3.6) є двоїстою або спряженою до задачі (3.1)—(3.3), яку називають прямою (основною, початковою). Поняття двоїстості є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів. Дійсно, не важко переконатися, що двоїста задача до (3.4)—(3.6) збігається з початковою. Тому кожну з них можна вважати прямою, а іншу — двоїстою.