Канонічна форма ЗЛП - завдання лінійного програмування виду ax = b де a - матриця коефіцієнтів, b - вектор обмежень.
Інструкція. Виберіть кількість змінних і кількість рядків (кількість обмежень). Отримане рішення зберігається в файлі Word.
Математична модель ЗЛП називається основний. якщо обмеження в ній представлені у вигляді рівнянь за умови невід'ємності змінних.
Математична модель називається канонічною. якщо її система обмежень представлена у вигляді системи m лінійно незалежних рівнянь (ранг системи r = m), в системі виділено одиничний базис. визначені вільні змінні і цільова функція виражена через вільні змінні. При цьому праві частини рівнянь невід'ємні (bi ≥ 0).
Змінні, що входять в одне з рівнянь системи з коефіцієнтом один і відсутні в інших рівняннях називаються базисними невідомими. а всі інші - вільними.
Рішення системи називається базисним. якщо в ньому вільні змінні рівні 0, і воно має вигляд:
Xбаз = (0, 0; b1. ..., bm), f (Xбаз) = c0
Базисне рішення є кутовий точкою безлічі рішень системи, тобто визначає вершину багатокутника рішень моделі. Серед таких рішень знаходиться і то, при якому цільова функція приймає оптимальне значення.
Базисне рішення називається опорним, якщо воно допустимо, тобто всі праві частини рівнянь системи (або нерівностей) позитивні bi ≥ 0.
Компактна форма канонічної моделі має вигляд:
AX = b
X ≥ 0
Z = CX (max)
Поняття допустимого рішення, області допустимих рішень, оптимального рішення задачі лінійного програмування.
Визначення 1. Вектор X, що задовольняє системі обмежень ЗЛП, в тому числі і умов невід'ємності, якщо вони є, називається допустимим рішенням ЗЛП.
Визначення 2. Сукупність усіх допустимих рішень утворює область допустимих рішень (ОДР) ЗЛП.
Визначення 3. Допустиме рішення, для якого цільова функція досягає максимуму (або мінімуму), називається оптимальним рішенням.
Приклад №1. Наступну задачу ЛП привести до канонічного виду: F (X) = 5x1 + 3x2 → max при обмеженнях:
2x1 + 3x2 ≤20
3x1 + x2 ≤15
4x1 ≤16
3x2 ≤12
Модель записана в стандартній формі. Введемо балансові невід'ємні змінні x3. x4. x5. x6. які додамо до лівих частинах обмежень-нерівностей. У цільову функцію все додаткові змінні введемо з коефіцієнтами, рівними нулю:
У першому нерівності сенсу (≤) вводимо базисну змінну x3. У 2-му нерівності сенсу (≤) вводимо базисну змінну x4. У третьому нерівності вводимо базисну змінну x5. В 4-му нерівності - базисну змінну x6. Отримаємо канонічну форму моделі:
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 20
3x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 15
4x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 = 16
0x1 + 3x2 + 0x3 + 0x4 + 0x5 + 1x6 = 12
F (X) = 5x1 + 3x2 + 0x3 + 0x4 + 0x5 + 0x6 → max