Питання до захисту лабораторної роботи

1. Основні етапи процесу моделювання.

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

3. Виробничі функції та їх використання.

4. Форми запису задач лінійного програмування.

5. Двоїстість задач лінійного програмування. Правила побудови двоїстих задач.

6. Загальна постановка транспортної задачі.

7. Збалансованість транспортної задачі.

8. Методи побудови початкових розв'язків транспортної задачі.

Лабораторна робота № 4. Вирішення завдань оптимізації з обмеженнями з використанням програм Excel

Мета роботи — освоїти роботу з програмами «Пошук рішення» та методику складання лінійних рівнянь для вирішення задач оптимізації з обмеженнями та практичне їх вирішення з застосуванням ПЕОМ.

Відведений час на виконання роботи — 4 години.

Теоретичні відомості. Вираз виду

(4.1)

називають лінійним рівнянням з невідомими.

Вираз виду

(4.2)

де - це один із знаків , називають лінійною нерівністю.

Систему рівнянь виду (4.1) називають системою лінійних рівнянь (СЛР):

(4.3)

Систему нерівностей виду (4.2) називають системою лінійних нерівностей (СЛН):

(4.4)

Систему рівнянь (4.3) можна представити у векторній формі:

,

де , ,…, ,

та у матричній формі:

, де , , .

Аналогічно можна представити і СЛН (4.4).

Якщо , то матимемо відповідно однорідну систему лінійних рівнянь або нерівностей.

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

Вектор називають лінійною комбінацією векторів , якщо .

СЛР (4.3) сумісна, якщо вона має хоча б один розв’язок, у противному випадку СЛР – несумісна.

СЛР (4.3) визначена, якщо вона має лише один розв’язок, у противному випадку СЛР – невизначена.

Під розв’язком СЛР розуміють вектор , який перетворює всі рівності системи в правильні числові рівності.

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

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

(4.5)

за умов:

( 4.6)

…, . (4.7)

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

Для загальної задачі лінійного програмування використовуються такі поняття.

Вектор , координати якого задовольняють систему обмежень (4.6) та умови невід’ємності змінних (4.7), називається допустимим розв’язком (планом) задачі лінійного програмування .

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

Опорний план , називається невиродженим, якщо він містить точно додатних змінних, інакше він вироджений.

Опорний план , за якого цільова функція (4.5) досягає максимального (чи мінімального) значення, називається оптимальним розв’язком (планом) задачі лінійного програмування.