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

Задача про використання сировини

З математичної точки зору ця задача є узагальненням тієї, котра розглянута в попередньому параграфі. Формулюється вона так.

Підприємство випускає продукцію n видів , на виготовлення якої витрачається сировина m видів , запаси котрої на підприємстві дорівнюють відповідно . Відомі витрати сировини S_i на виробництво одиниці продукції (i = ; j =). Вартість одиниці продукції дорівнює (j =). Потрібно скласти такий план випуску продукції, при якому прибуток від реалізації продукції був би найбільшим.

Складемо математичну модель задачі.

Нехай - кількість одиниць продукції (j =).

Математична модель має вигляд:

f =→ max

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

(2.0)

2.3. Задачі складання раціону (задача про дієту)

Для відгодівлі тварини використовується n видів кормів, що містять m видів поживних речовин. Нехай- вміст i- ої поживної речовини в одному кілограмі j - го виду корму - вартість одного кілограма j-ro виду корму Мінімальна добова потреба тварини в i-ої поживній речовині дорівнює . Необхідно скласти найбільш дешевий раціон потрібної поживності.

Позначимо через x_j кількість кілограмів корму j-го виду.

Очевидно, математична модель задачі така.

f = → min

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

Лінійним обмеженням, накладеним на змінні , називається співвідношення одного з наступних трьох типів:

де - дійсні числа.

Наприклад, співвідношення 2х -≤ 1 або ≥ 0 є

лінійними, а співвідношення ≥ 3 або sin x₁ ≤ не є лінійними.

Загальна постановка задачі лінійного програмування (ЗЛП) полягає в наступному.

Дано деяку лінійну функцію

f =_n (2.1)

і деяка система лінійних обмежень, накладених на змінні :

(2.2)

Потрібно знайти такі значення змінних, які

задовольняли б обмеженням (2.2) і при цьому обертали б в оптимум (max і min) функцію (2.1).

Функція (2.1) називається цільовою. Кожний набір значень змінних, при яких задовольняються обмеження (2.2), називається припустимим рішенням або припустимим планом ЗЛП. Сукупність всіх припустимих рішень називається областю припустимих рішень (ОПР).

Наведені в параграфах 2.1, 2.2, 2.3 задачі є задачами лінійного програмування.

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

Говорять, що ЗЛП розв'язна, якщо вона має оптимальний план. У протилежному випадку задача називається нерозв'язною.

ЗЛП може бути нерозв'язною тільки з наступних двох причин:

а) ОПР порожня;

б) ОПР непорожня, але цільова функція не обмежена на ОПР зверху, якщо в ЗЛП шукається її максимум, або - не обмежена знизу, якщо в ЗЛП шукається мінімум цільової функції.

Наприклад, задача: f =min

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

нерозв'язна через порожнечу ОПР.

Задача ж f =max при обмеженні

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

Дата добавления: 2014-01-07