Каноническая форма задач линейного программирования

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

В каждой задаче ЛП ищутся значения переменных при условии, чтобы:

  • эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
  • при этих значениях целевая функция обращалась бы в минимум или максимум.
Инструкция. Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word.
Количество переменных
Количество строк (количество ограничений)
Одним из универсальных методов ЛП является симплексный метод, который, однако, можно применять, если задача ЛП имеет каноническую форму.

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

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

  • неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;
  • если целевая функция F→max (максимизируется), она заменяется на функцию –F→ min (которая минимизируется).
загрузка...