Короткі теоретичні відомості

Відведений час: 2 год.

Різні форми запису ЗЛП

Мета: ознайомити студентів із різними формами запису задач лінійного програмування, навчати переходити від однієї форми запису до іншої (зокрема, зведення ЗЛП до канонічного виду).

Завдання для практичного заняття:

1. Пригадайте основні теоретичні питання теми.

2. Орієнтовні запитання та завдання:

- запишіть загальний випадок ЗЛП, за допомогою знака «», векторно-матричному та векторній формі;

- що називається оптимальним розв’язком ЗЛП?

- назвіть вимоги до написання ЗЛП у канонічній формі?

3. Виконайте індивідуальне завдання.

В загальному випадку задача лінійного програмування формулюється наступним чином: серед розв’язків системи лінійних рівнянь з невідомими

(2.18)

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

(2.19)

приймає максимальне значення.

Розв’язок , при якому функція досягає максимуму, називається оптимальним розв’язком або оптимальним планом задачі.

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

Систему (2.18) можна записати в більш компактній векторній формі: розглянемо вектор в -мірному просторі

, , , , ,

тоді (2.18) приймає вигляд:

.

Часто для системи обмежень (2.18) використовують матрично-векторний спосіб запису:

де

, ,

– відповідно матриця коефіцієнтів біля невідомих, вектор-стовпчик з невідомих та вектор-стовпчик з правих частин рівнянь системи обмежень.

Матрицю називають матрицею системи або основною матрицею системи обмежень (2.18). Розглядають також матрицю

,

яку називають розширеною матрицею системи обмежень (2.18).

Якщо задача лінійного програмування записана у вигляді (2.18)–(2.19), то її називають канонічною.

Дата добавления: 2017-02-01