Структурні моделі основних задач мп

Класична задача МП. Мета: максималізація цільової функції при заданих обмеженнях

при умові, що ,

(2)

де - функції обмежень (відомі неперервно диференційовані функції);

- константи обмежень.

В розгорнутому вигляді обмеження є рівностями:

. . .

(3)

Задача нелінійного програмування (НП) передбачає систему обмежень двох типів:

умов-обмежень у вигляді нерівностей

;

(4)

граничних умов (невід’ємності)

;

(5)

тобто

Таким чином, задача НП записується так:

при умові, що

(6)

Задача лінійного програмування (ЛП).

Цільова функція даної задачі – лінійна:

(7)

де - заданий вектор – рядок констант

(8)

Система обмежень двох типів:

умови – обмеження у вигляді лінійних нерівностей

(9)

граничні умови

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

при умові, що

(10)

де

(11)

В операторній формі:

(12)

3.3. Приклад розгорнутої моделі задачі лп

Порядок створення економіко-математичної моделі

1. Структурна модель.

2. Числова (розширена, розгорнута) модель, тобто запевнення конкретним числовим змістом.

Розглянемо приклад: нехай підприємство виробляє два види продукції: і , для яких використовують сировину (ресурси) і . Вартість одиниці кожного продукту відповідно і : = 3 од., = 2 од. Знайти скільки треба виробити продукції і , щоб отримати доход і вкластися в обмеження по сировині: для використати не більше ресурсів; для - не більше ресурсів і по забрудненню середовища: не більше доз.

Далі витрат сировини та забруднення середовища при виробництві одиниці продукту відповідно:

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

Ресурс			Обмеження
	6	3	 12
	2	4	 10
Забруднення	2	0	 6
	3	2

Структурна модель:

(13)

Розгорнута числова модель:

(14)

3.4. Графоаналітичний метод

Метод використовують, коли задача лінійного програмування містить дві змінні: і (можна 3 змінні  декартовий простір ). Наприклад, система рівнянь (13).

Методика розв’язання задачі:

1).Побудувати декартову систему координат ( ) – тільки І чверть в силу обмежень

2).Будуємо область допустимих значень відповідно нерівностям-обмеженням, які представляють собою напівплощини. На перетині всіх півплощин знаходиться область .

3). Проводимо лінії рівня функції , які визначаються видом рівняння

,

(15)

де .

Рівняння (15) можна записати у вигляді:

.

(16)

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

(17)

тобто в напрямку нормалі до лінії рівня.

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

відповідає точці перетину лінії рівня з дальньою вершиною (стороною) області (точка виходу).

Значення змінних і указують перпендикуляри до осей і , опущені з точки екстремуму.

Закономірності:

1). Оптимальне рішення завжди знаходиться на границі області допустимих значень і, як правило, у вершині багатокутника.

2). Рішення може бути не єдиним, якщо лінія рівня паралельна стороні багатокутника.

3). Задача може не мати рішення, коли в напрямку росту функції допустима область не обмежена.

Розв’язок задачі – прикладу:

Аналогічно: на перетині ліній.

та
   .