Переход к канонической форме ЗЛП
Каноническая форма ЗЛП - задача линейного программирования видаax = b, где a - матрица коэффициентов, b - вектор ограничений.
Назначение сервиса. Онлайн-калькулятор предназначен для перехода ЗЛП к КЗЛП. Приведение задачи к канонической форме означает, что все ограничения будут иметь вид равенств, путем ввода дополнительных переменных.
Если на какую-либо переменную xj не наложено ограничение, то она заменяется на разность дополнительных переменных, xj = xj1 - xj2, xj1 ≥ 0, xj2 ≥ 0.
Математическая модель ЗЛП называется основной, если ограничения в ней представлены в виде уравнений при условии неотрицательности переменных.
Математическая модель называется канонической, если ее система ограничений представлена в виде системы 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 – сбалансированная транспортная задача с системой ограничений (1) и целевой функцией (2).
Однако в большинстве экономических задач чаще всего в систему ограничений первоначально входят не только уравнения, а и неравенства.
Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных.
Система ограничений (3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y1≥ 0, y2≥ 0, y3≥ 0, y4 ≥ 0, можно перейти к системе ограничений:
Эти дополнительные переменные y i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).
Например, если бы машины первого вида работали все 18 ч, то x + y = 18, следовательно, y1 = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y<18. В этом случае y1 приобретает положительное значение и может рассматриваться как неиспользованный лимит времени. Например, зная решение этой задачи из пункта 3.3.2, x = 12, y = 6, мы можем из системы ограничений (3.9) сделать вывод, что y1 = y2 = y3 = 0, а y4 = 12 – 6 = 6. Т. е. машины первого, второго, третьего вида используют свое рабочее время полностью.
А вот четвертая машина загружена лишь наполовину, 6 часов, и при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой, сдать в аренду на это время и т.д.
Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.
Рассмотрим задачу о смеси. Система ограничений имеет вид:
Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y1, y2, y3≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:
Переменные yi также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y1 будет означать количество излишнего вещества А в смеси, y2 –количество излишков вещества В в смеси, y3 – излишки С в смеси.
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения maxF = –min (–F). Посмотрите на рисунок: если в какой-то точке x= x0 функция y= F(x) достигает своего максимума, то функция y= –F(x), симметричная ей относительно оси OX, в этой же точке x0 достигнет минимума, причем Fmax = – (–Fmin) при x = x0.
Вывод. Для представления задачи ЛП в канонической форме необходимо:
- неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;
- если целевая функция F→max (максимизируется), она заменяется на функцию –F→ min (которая минимизируется).
Пример №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)
Пример №3. Привести к канонической форме следующую ЗЛП.
F = 2x1 - x2 + 4x3 -2x4 → min
при ограничениях:
7x1 –x2 +5x3 + x4 = -10
3x1 +5x2 -9x3 + 2x4 = 6
x1 –x2 -2x3 + 6x4 ≥ 7
x1 +x2 -5x3 ≤ 11
7x1 –x2 -3x3 - x4 ≤ 9
x1 ≥0 , x2 ≥0 (обратите внимание, что переменные x3 и x4 имеют произвольный знак)
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции
- F = -2x1 + x2 - 4x3 +2x4 → max
2. В левые части трех последних неравенств внести дополнительные переменные x5, x6, x7 со знаком плюс или минус в зависимости от знака неравенства.
7x1 –x2 +5x3 + x4 = -10
3x1 +5x2 -9x3 + 2x4 = 6
x1 –x2 -2x3 + 6x4 –x5 = 7
x1 +x2 -5x3 +x6 = 11
7x1 –x2 -3x3 - x4 +x7 = 9
x1 ≥0 , x2 ≥0, x5 ≥0 , x6 ≥0, x7 ≥0
3. Так как переменные x3 и x4 произвольного знака, то они заменяются разностями неотрицательных переменных.
7x1 –x2 +5(x8 – x9) + (x10 – x11) = -10
3x1 +5x2 -9(x8 – x9) + 2(x10 – x11) = 6
x1 –x2 -2(x8 – x9) + 6(x10 – x11) –x5 = 7
x1 +x2 -5(x8 – x9) +x6 = 11
7x1 –x2 -3(x8 – x9) - (x10 – x11) +x7 = 9
x1 ≥0 , x2 ≥0, x5 ≥0 , x6 ≥0, x7 ≥0 , x8 ≥0, x9 ≥0 , x10 ≥0, x11 ≥0
4. Соответствующая целевая функция примет вид:
- F = -2x1 + x2 - 4(x8 – x9) +2(x10 – x11) → max
см. также Как привести каноническую задачу линейного программирования к стандартной форме
Пример №2. Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.
