Форми запису задач лінійного програмування, Геометрична інтерпретація задачі лінійного програмування - Розв'язання задач математичного програмування

1. За допомогою знака суми "".

(2.6)

2. У векторно-матричному вигляді:

Max(min) Z = CX

АХ = А0; (2.7)

Х ? 0,

Де

, ,

Матриця коефіцієнтів; вектор змінних; вектор вільних членів;

С = (С1, с2, ..., сП) -- вектор коефіцієнтів при змінних у цільовій функції.

3. У векторній формі:

Max(min)Z = CX

A1X1 + A2X2 + ... + ANXN = A0; (2.8)

X ?0,

Де

є векторами коефіцієнтів.

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

Розглянемо на площині Х1Оx2 Сумісну систему лінійних нерівностей:

(2.9)

Сукупність цих точок (розв'язків) називають Багатокутником розв'язків, або Областю допустимих планів (розв'язків) задачі лінйного програмування. Це може бути точка (єдиний розв'язок), відрізок, промінь, багатокутник, необмежена багатокутна область.

Якщо в системі обмежень (2.9) буде три змінних, то спільну частину називають Багатогранником розв'язків. Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Нехай у системі обмежень (2.9) кількість змінних більша, ніж три: Х1, Х2,... ХN, якщо система обмежень сумісна, то за аналогією з тривимірним простором вона утворює спільну частину в N-вимірному просторі -- Опуклий багатогранник допустимих розв'язків.

Цільову функцію

В П-вимірному просторі основних змінних можна геометрично інтерпретувати як сім'ю паралельних гіперплощин, положення кожної з яких визначається значенням параметра Z.

Приклад:

Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га. Показники вирощування цих культур у табл.

Показник (із розрахунку на 1 га)

Озима пшениця

Цукрові буряки

Наявний ресурс

Затрати праці, людино-днів

5

25

270

Затрати праці механізаторів, людино-днів

2

8

80

Урожайність, тонн

3,5

40

--

Прибуток, тис. грн.

0,7

1

--

Критерієм оптимальності є максимізація прибутку.

Позначення:

Х1 -- площа посіву озимої пшениці, га;

Х2 -- площа посіву цукрових буряків, га.

Max Z = 0,7X1 + X2 (2.10)

За умов: X1 + X2 ? 20; (2.11)

    5X1 + 25X2 ? 270; (2.12) 2X1 + 8X2 ? 80; (2.13)

X2 ? 5; (2.14)

X1 ? 0, X2 ? 0. (2.15)

Похожие статьи




Форми запису задач лінійного програмування, Геометрична інтерпретація задачі лінійного програмування - Розв'язання задач математичного програмування

Предыдущая | Следующая