Переход к канонической форме ЗЛП

Каноническая форма ЗЛП - задача линейного программирования вида ax = b где a - матрица коэффициентов, b - вектор ограничений.

Назначение сервиса. Онлайн-калькулятор предназначен для перехода ЗЛП к КЗЛП. Приведение задачи к канонической форме означает, что все ограничения будут иметь вид равенств, путем ввода дополнительных переменных.
Если на какую-либо переменную xj не наложено ограничение, то она заменяется на разность дополнительных переменных, xj = xj1 - xj2, xj1 ≥ 0, xj2 ≥ 0.

Инструкция. Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле 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

Пример №2. Найти два опорных решения системы
x1 + 2x4 – 2x5 = 4
x3 + 3x4 + x5 = 5
x2 + 3x5 = 2

Ответ: X = (4;2;5;0;0)

загрузка...