К канонической форме записи можно привести любую. Задачи линейного программирования (ЗЛП)

В исходной постановке ЗЛП могут допускать различные формы записи. Так, в одних задачах требуется максимизировать целевую функцию, в других - минимизировать; некоторые линейные ограничения могут иметь вид равенств, другие - неравенств и т.д.

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

Говорят, что ЗЛП записана в канонической форме, если она имеет следующий вид:

Отметим следующие особенности канонического вида:

1) требуется минимизировать целевую функцию;

2) все линейные ограничения, кроме требований неотрицательности переменных, имеют вид равенств;

на все переменные наложены требования неотрицательности.

Покажем, что любую ЗЛП можно привести к каноническому виду.

1) Если в ЗЛП требуется максимизировать целевую функцию f, то положим g = - f и потребуем минимизировать функцию g. Получится новая ЗЛП, которая эквивалентна исходной в том смысле, что каждое оптимальное решение исходной задачи будет оптимальным решением новой задачи и наоборот.

2) Предположим, что в ЗЛП есть линейное ограничение вида

Заменим такое ограничение следующими двумя ограничениями:

где z - новая переменная, которая в целевую функцию вводится с коэффициентом 0 (иначе говоря, переменная z не вводится в целевую функцию). Значение переменной z можно не учитывать после решения новой задачи.

Аналогично, ограничение вида заменяется двумя ограничениями:

3) Предположим, что в ЗЛП не ко всем переменным предъявлено требование неотрицательности. Тогда каждую, переменную , на которую не наложено требование неотрицательности, представим в виде разности двух неотрицательных переменных:

Каждое вхождение переменной в целевую функцию или ограничения заменим разностью
. Решив новую задачу с помощью (2.6), вернемся к прежним переменным.

Указанными приемами любая ЗЛП приводится к каноническому виду.

Пример. Привести к каноническому виду

Проделаем описанные действия.

Теперь получим ЗЛП в каноническом виде:

2.7. Понятие опорного плана злп.

Пусть ВЛП задана в каноническом виде (2.3 - 2.5). Предположим, что система уравнений (2.4) приведена к жордановой форме с неотрицательными правыми частями:

(2.6)

где
.

Приравняв к нулю свободные переменные, получим базисное решение системы (2.4)

В силу условия
набор значений переменных (2.7) удовлетворяет и ограничениям (2.5). Поэтому (2.6) являетсядопустимым решением ЗЛП .

Допустимое решение (2.7) называется базисным допустимым решением или опорным планом ЗЛП. При этом говорят, что переменные
образуют допустимый базис.

Оказывается, что если ОДР изобразить геометрически, то каждый опорный план ЗЛП соответствует вершине многогранника. Поэтому справедлива следующая теорема.

Если ЗЛП разрешима, то существует оптимальный опорный план.

3. Симплексный метод решения злп

3.1. Общая характеристика и основные этапы симплекс – метода

Основоположниками симплекс-метода являются советский математик Л.В. Канторович и американский математик Дж. Данциг.

Симплекс-методом можно решить любую ЗЛП или обнаружить ее неразрешимость. Многие специальные классы ЗЛП можно решить другими, более эффективными для этих классов методами. Однако преимущество симплекс-метода - его универсальность. Почти для всех ЭВМ разработаны стандартные программы для решения ЗЛП симплекс - методом.

Опишем общую идею симплекс-метода.

Считаем, что ЗЛП записана в каноническом виде и целевую функцию нужно минимизировать. Как мы уже знаем, оптимальный план следует искать среди опорных планов ЗЛП. Симплекс-метод не перебирает все опорные планы (что было бы часто невозможно из-за их огромного количества), а, начиная с некоторого исходного опорного плана, он последовательно переходит к другим опорным планам с уменьшением целевой функции. Симплекс-метод прекращает свою работу тогда, когда либо будет найден оптимальный опорный план, либо установлена неразрешимость задачи.

При решении ЗЛП симплекс-методом можно выделить следующие этапы:

1) приведение ЗЛП к каноническому виду;

2) приведение системы линейных уравнений к жордановой форме с неотрицательными правыми частями с одновременной проверкой на неразрешимость ЗЛП из-за противоречивости системы линейных ограничений;

3) исследование опорного плана на оптимальность;

4) исследование ЗЛП на неразрешимость из-за неограниченности снизу на ОДР целевой функции;

5) переход к новому, "лучшему" опорному плану.

Запись целевой функции и системы ограничений в различных задачах линейного программирования неодинаков: в одних задачах требуется найти минимум целевой функции, а в других – максимум; в одних случаях искомые переменные зависят от одного индекса, а в других – от двух; в одних задачах ограничения заданы в виде системы линейных неравенств, а в других – в виде системы линейных уравнений. На практике возможны также задачи, в которых часть ограничений имеет вид линейных неравенств, а часть – линейных уравнений. Также не во всех задачах может требоваться неотрицательность переменных .

Учет такого разнообразия задач линейного программирования требует разработки специальных методов для решения отдельных их классов. Мы же сосредоточим свое внимание на изучении общих свойств и методов линейного программирования, записанных в так называемой канонической форме.

Если в задаче линейного программирования система исходных ограничений приобретает вид уравнений типа

и нужно найти максимум линейной целевой функции

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

Любую задачу линейного программирования можно легко свести к канонической форме. В общем случае для этого достаточно уметь, во-первых, свести задачу минимизации целевой функции к задаче ее максимизации, во-вторых, переходить от ограничений-неравенств к ограничениям-равенствам, и в-третьих, менять те переменные, которые не подчинены условию неотрицательности.

В том случае, когда нужно найти минимум функции , можно перейти к нахождению максимума функции , поскольку справедливо утверждение:
.

Ограничение-неравенство исходной задачи, которое имеет вид «» , можно превратить в ограничение-уравнение путем добавления к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида «»– путем вычитания из его левой части дополнительной неотрицательной переменной.

Заметим, что количество введенных дополнительных неотрицательных переменных всегда равно количеству неравенств в исходной системе ограничений.

Введены дополнительные переменные имеют вполне конкретный экономический смысл. Так, если в ограничениях исходной задачи линейного программирования отражаются расходы и наличие производственных ресурсов, то числовое значение дополнительной переменной показывает объем соответствующего неиспользованного ресурса.

Отметим также, что если некоторая переменная не подчиняется условию неотрицательности, то ее нужно заменить двумя неотрицавтельными переменными и , приняв
.

Пример . Записать в канонической форме следующую задачу линейной оптимизации: найти минимум функции
при ограничениях

Решение

В данной задаче нужно найти минимум целевой функции, а система ограничений включает четыре неравенства. Для того, чтобы записать ее в канонической форме, нужно перейти от ограничений-неравенств к ограничениям-уравнениям, а также превратить целевую функцию.

Так как количество неравенств, входящих в систему ограничений задачи, равно четырем, то этот переход должен быть осуществлен с введением четырех дополнительных неотрицательных переменных. При этом во втором и четвертом неравенствах стоит знак «» , поэтому к их левой части дополнительные переменные добавляем. В первом и третьем неравенствах – знак «», значит от их левой части дополнительные переменные вычитаем.

Также превращаем целевую функцию, поменяв все знаки на противоположные, и находим ее максимум.

Таким образом, данная задача линейного программирования будет записана в следующем каноническом виде:

найти максимум функции

при ограничениях

В общем случае задача линейного программирования записывается так, что ограничениями являются как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольно изменяющимися. В том случае, когда все ограничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической. Она может быть представлена в координатной, векторной или матричной записи.

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

.

В более компактной форме данную задачу можно записать, используя знак суммирования,

(1.7)

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

(1.8)

где ,

.

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

(1.9)

, .

Здесь А – матрица коэффициентов системы уравнений, Х – матрица-столбец переменных задачи, – матрица-столбец правых частей системы ограничений.

Нередко используются задачи линейного программирования, называемые симметричными , которые в матричной записи имеют вид

(1.10)

(1.11)

1.4. Приведение общей задачи линейного программирования
к канонической форме

В большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных. Однако при составлении математических моделей экономических задач ограничения в основном формируются в системы неравенств, поэтому необходимо уметь переходить от системы неравенств к системе уравнений. С этой целью докажем следующую теорему.

Теорема 1.1. О замене неравенства уравнением. Каждому решению неравенства

соответствует единственное решение уравнения

и неравенства

, (1.14)

и, наоборот, каждому решению уравнения (1.13) и неравенства (1.14) соответствует единственное решение неравенства (1.12).

Доказательство. Пусть – решение неравенства (1.12), тогда . Обозначим разность правой и левой частей этого неравенства через , т. е.

Очевидно . Подставим в уравнение (1.13) вместо переменных значения , получим

Таким образом, удовлетворяет уравнению (1.13) и неравенству (1.14). Значит доказана первая часть теоремы.

Пусть теперь удовлетворяет уравнению (1.13) и неравенству (1.14), т. е. имеем

И

Отбрасывая в левой части последнего равенства неотрицательную величину , получаем

т. е. удовлетворяет неравенству (1.12). Теорема доказана.

Если неравенство , то дополнительную неотрицательную переменную необходимо ввести в его левую часть со знаком минус, т. е. .

Неотрицательные переменные, вводимая в ограничения неравенства для превращения их в уравнения, называются дополнительными переменными . Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значение.

В том случае, когда задача имеет произвольно изменяющиеся переменные, то любую такую переменную заменяют разностью двух неотрицательных переменных, т. е. , где и .

Иногда возникает необходимость перейти в задаче от нахождения минимума к нахождению максимума или наоборот. Для этого достаточно изменить знаки всех коэффициентов целевой функции на противоположные, а в остальном задачу оставить без изменения. Оптимальные решения полученных таким образом задач на максимум и минимум совпадают, а значения целевых функций на оптимальных решениях отличаются только знаком.

Пример 1.1. Привести к каноническому виду задачу линейного программирования.

Д

Решение . Перейдем к задаче на отыскание максимума целевой функции. Для этого изменим знаки коэффициентов целевой функции. Для превращения в уравнения второго и третьего неравенств системы ограничений введем неотрицательные дополнительные переменные (на математической модели эта операция отмечена буквой Д). Переменная вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид . Переменная вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид . В целевую функцию переменные вводятся с коэффициентом, равным нулю. Переменную , на которую не наложено условие неотрицательности заменяем разностью , . Записываем задачу в каноническом виде

В некоторых случаях возникает необходимость приведения канонической задачи к симметричной задаче. Рассмотрим пример.

Пример 1.2. Привести к симметричному виду задачу линейного программирования

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

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

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 2 3 4 5 6 7 8 9 10

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

Математическая модель ЗЛП называется основной , если ограничения в ней представлены в виде уравнений при условии неотрицательности переменных.

Математическая модель называется канонической , если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r=m), в системе выделен единичный базис , определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны (b i ≥ 0).

Переменные, входящие в одно из уравнений системы с коэффициентом один и отсутствующие в других уравнениях называются базисными неизвестными , а все другие - свободными .

Решение системы называется базисным , если в нем свободные переменные равны 0, и оно имеет вид:
X баз = (0, 0; b 1 , …, b m), f(X баз) = c 0

Базисное решение является угловой точкой множества решений системы, т.е. определяет вершину многоугольника решений модели. Среди таких решений находится и то, при котором целевая функция принимает оптимальное значение .

Базисное решение называется опорным, если оно допустимо, т.е. все правые части уравнений системы (или неравенств) положительны b i ≥ 0.

Компактная форма канонической модели имеет вид:
AX = b
X ≥ 0
Z = CX(max)

Понятие допустимого решения, области допустимых решений, оптимального решения задачи линейного программирования .
Определение 1 . Вектор X, удовлетворяющий системе ограничений ЗЛП, в том числе и условиям неотрицательности, если они имеются, называется допустимым решением ЗЛП.
Определение 2 . Совокупность всех допустимых решений образует область допустимых решений (ОДР) ЗЛП.
Определение 3 . Допустимое решение, для которого целевая функция достигает максимума (или минимума), называется оптимальным решением.

Пример №1 . Следующую задачу ЛП привести к каноническому виду: F(X) = 5x 1 + 3x 2 → max при ограничениях:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Модель записана в стандартной форме. Введем балансовые неотрицательные переменные x 3 , x 4 , x 5 , x 6 , которые прибавим к левым частям ограничений-неравенств. В целевую функцию все дополнительные переменные введем с коэффициентами, равными нулю:
В первом неравенстве смысла (≤) вводим базисную переменную x 3 . Во 2-ом неравенстве смысла (≤) вводим базисную переменную x 4 . В третьем неравенстве вводим базисную переменную x 5 . В 4-м неравенстве - базисную переменную x 6 . Получим каноническую форму модели:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → max

Пример №2 . Найти два опорных решения системы
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2

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

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

• эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
• при этих значениях целевая функция обращалась бы в минимум или максимум.

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Одним из универсальных методов ЛП является симплексный метод, который, однако, можно применять, если задача ЛП имеет каноническую форму.

Определение . Задача ЛП имеет каноническую форму, если все ограничения системы состоят только из уравнений (кроме неравенств, выражающих неотрицательность переменных) и целевую функцию необходимо минимизировать.
Примером такой задачи ЛП в канонической форме является задача 1 – сбалансированная транспортная задача с системой ограничений (1) и целевой функцией (2).
Однако в большинстве экономических задач чаще всего в систему ограничений первоначально входят не только уравнения, а и неравенства.

Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных.
Система ограничений (3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, можно перейти к системе ограничений:

Эти дополнительные переменные y i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i -го вида).
Например, если бы машины первого вида работали все 18 ч, то x + y = 18, следовательно, y 1 = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y <18. В этом случае y 1 приобретает положительное значение и может рассматриваться как неиспользованный лимит времени. Например, зная решение этой задачи из пункта 3.3.2, x = 12, y = 6, мы можем из системы ограничений (3.9) сделать вывод, что y 1 = y 2 = y 3 = 0, а y 4 = 12 – 6 = 6. Т. е. машины первого, второго, третьего вида используют свое рабочее время полностью. А вот четвертая машина загружена лишь наполовину, 6 часов, и при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой, сдать в аренду на это время и т.д.
Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.

Рассмотрим задачу о смеси. Система ограничений имеет вид:
Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y 1 , y 2 , y 3 ≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:
Переменные y i также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y 1 будет означать количество излишнего вещества А в смеси, y 2 –количество излишков вещества В в смеси, y 3 – излишки С в смеси.
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения max F = –min (– F). Посмотрите на рисунок: если в какой-то точке x = x 0 функция y = F (x ) достигает своего максимума, то функция y = –F (x ), симметричная ей относительно оси OX , в этой же точке x 0 достигнет минимума, причем F max = – (–F min) при x = x 0 .

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

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