Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

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

Каноническая форма ЗЛП - задача линейного программирования вида 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 – сбалансированная транспортная задача с системой ограничений (1) и целевой функцией (2).
Однако в большинстве экономических задач чаще всего в систему ограничений первоначально входят не только уравнения, а и неравенства.

Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных.
Система ограничений (3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y1≥  0, y2≥  0, y3≥  0, y≥  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.

Вывод. Для представления задачи ЛП в канонической форме необходимо:

Пример №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. Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.

Болит горло
Как быстро вылечить ангину, гланды, тонзиллит
Природные средства, проверенные временем и врачами
Подробнее
ЕГЭ по математике
Yandex.Просвещение представляет бесплатные видеокурсы по ЕГЭ с возможностью прохождения тестов
Подробнее
Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн