Различные формы записи ЗЛП (общая, каноническая, симметрическая). Симплексный метод решения задачи линейного программирования

Задача линейного программирования вида 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 (которая минимизируется).

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

Канонической задачей линейного программирования (КЗЛГТ) будем называть следующую задачу:

при ограничениях, имеющих вид равенств,

Если для задачи в форме (2.3.1)-(2.3.4) выполняется условие т = п, то ее решение сводится к решению системы уравнений

• (2.3.2) . При этом задача не будет иметь решений, если условие
• (2.3.3) не выполняется или система уравнений не имеет решения.

условие т

• 1. Для перехода от задачи максимизации целевой функции (2.3.1) к задаче минимизации достаточно взять все коэффициенты Cj целевой функции с обратными знаками и решить полученную задачу на максимум. После нахождения максимума значение целевой функции надо взять с обратным знаком. Оптимальное решение останется прежним.
• 2. Для перехода от ограничения типа «меньше или равно» к равенству в него необходимо со знаком «плюс»:

3. Для перехода от ограничения типа «больше или равно» к равенству в него необходимо ввести дополнительную неотрицательную переменную со знаком «минус»:

При этом в каждое неравенство вводится своя (п + /)-я дополнительная переменная.

• 4. Все равенства, имеющие отрицательные свободные члены, делятся на -1, для того чтобы выполнялось условие (2.3.4).
• 5. Если на некоторую переменнуюXj не накладывается условие неотрицательности , то делают замену переменных Xj=х". - х" x"j > 0, х"> 0. В преобразованной задаче все переменные неотрицательные.

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

Пример 2.3.1. Преобразуем задачу, приведенную в примере 2.2.2, в каноническую форму. Целевая функция и система ограничений выглядят следующим образом:

Введем в первое неравенство дополнительную переменную jc 3 > 0 со знаком «плюс», во второе х 4 > 0 со знаком «минус» и в третье х 5 > 0 также со знаком «плюс». В результате получим систему ограничений задачи в канонической форме:

При этих ограничениях нужно найти максимальное значение функции:

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

Пример 2.3.2. Задача оптимального использования ресурсов (задача о коврах) [ 17 J.

В распоряжении фабрики имеется определенное количество ресурсов трех видов: труд (80 человекодней), сырье (480 кг) и оборудование (130 станкочасов). Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса, необходимых для производства одного ковра каждого вида, и о доходах, получаемых предприятием от единицы каждого вида товаров, приведена в табл. 2.3.1.

Требуется найти такой план выпуска продукции, при котором ее общая стоимость будет максимальной.

Экономико-математическая модель задачи Переменные : х х,х 2 , х 3 , х 4 - количество ковров каждого типа. Целевая функция - это общая стоимость продукции, которую необходимо максимизировать:

Ограничения по ресурсам :

Приведем задачу к канонической форме, вводя дополнительные переменные х 5 , х 6 и х 7:

Далее будет показано, что оптимальным планом выпуска продукции является вектор X* = (0; 30; 10; 0), значение целевой функции равно 150, т.е. для максимизации общей стоимости продукции необходимо выпустить 30 ковров второго вида и 10 ковров третьего вида. Подставим оптимальные значения вектора X в ограничения КЗЛП:

Получим, что ресурсы «труд» и «оборудование» используются полностью, ресурс «сырье» имеется в избытке:

В этом случае х в показывает, что сырья осталось 200 кг.

Таким образом, основные переменные x v х 2 , х 3 , х л означают количество ковров каждого типа, а дополнительные переменные х 5 , х 6 их 7 - объем недоиспользованных ресурсов.

Ответ. Оптимальный план выпуска продукции X* = (0; 30;

10; 0).

Планом , или допустимым решением , КЗЛП называется вектор X = (jc p х 2 ,..., х п ), удовлетворяющий условиям (2.3.2)-(2.3.4).

Если все компоненты базисного решения системы ограничений КЗЛП неотрицательны, то такое решение называется опорным решением или опорным планом. Число положительных компонент опорного плана не может превышать т.

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

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

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

Для отыскания оптимального плана достаточно исследовать только опорные планы. Верхняя граница количества опорных планов, содержащихся в задаче, определяется числом сочетаний С т п (см. параграф 1.4).

Пример 2.3.3. Получить решение задачи об оптимальном использовании ограниченных ресурсов (решить ЗЛ П):

Решение. Приведем задачу к каноническому виду путем введения дополнительных переменныхх 3 , х 4 и х 5:

Найдем все опорные планы системы ограничений данной КЗЛП (л? - 5; /77 - 3); их количество не превышает 10:

Используя метод Жордана - Гаусса (см. параграф 1.4), выписываем все базисные решения системы уравнений (табл. 2.3.2).

Номер базис ного решения	Базис						План

Среди десяти базисных решений пять опорных:

Указанным опорным планам на рис. 2.3.1 отвечают соответственно следующие угловые точки и значения ЦФ в них:

Рис. 2.3.1.

Согласно теории ЛП оптимальное решение содержится среди опорных планов.

Таким образом, максимальное значение, равное 2300, целевая функция достигает в точке В на опорном плане Х 5 = (70; 80; 0; 60; 0).

Ответ. Оптимальный план задачи: х { = 70, х 2 = 80, значение целевой функции f(x v х 2) = 2300.

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

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

• если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
• если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
• если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
• если некоторая переменная x j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
  x 3 = x 3 + - x 3 - , где x 3 + , x 3 - ≥ 0 .

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

min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Введем в каждое уравнение системы ограничений выравнивающие переменные x 4 , x 5 , x 6 . Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x 4 , x 6 вводятся в левую часть со знаком "+", а во второе уравнение переменная x 5 вводится со знаком "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что x 1 = x 1 " - x 7 , где x 1 " ≥ 0, x 7 ≥ 0 .

Подставляя данное выражение в систему ограничений и целевую функцию и, записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:

L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 " ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Условие оптимальности базисного плана канонической задачи ЛП. Симплекс-метод и его сходимость.

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

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

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

Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение.

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

Алгоритм симплексного метода

1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность.
Для этого заполняем симплексную таблицу 1.
Все строки таблицы 1-го шагазаполняем по данным системы ограничений и целевой функции.

Возможны следующие случаи при решении задач на максимум:

1. Если все коэффициенты последней строки симплекс-таблицы Dj ³ 0, то найденное

решение оптимальное.

2 Если хотя бы один коэффициент Dj £ 0, но при соответствующей переменной нет ни одного положительного оценочного отношения, то решение задачи прекращаем , так как F(X) ® ¥ , т.е.целевая функция не ограничена в области допустимых решений.

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

4. Если отрицательных коэффициентов в последней строке несколько, то в столбец базисной переменной (БП) вводят ту переменную , которой соответствует наибольший по абсолютной величине отрицательный коэффициент.

5. Если хотя бы один коэффициент Dk < 0 ,то k - тый столбец принимаем за ведущий.

6. За ведущую строку принимаем ту, которой соответствует минимальное отношение свободных членов bi к положительным коэффициентам ведущего, k – того столбца.

7. Элемент, находящийся на пересечении ведущих строк и столбца, называется ведущим элементом.

Заполняем симплексную таблицу 2:

· заполняем базисный столбец нулями и единицей

· переписываем ведущую строку, разделив ее на ведущий элемент

· если ведущая строка имеет нули, то в следующую симплекс-таблицу можно перенести соответствующие столбцы

· остальные коэффициенты находим по правилу “прямоугольника”

Получаем новое опорное решение, которое проверяем на оптимальность:

Если все коэффициенты последней строки Dj ³ 0, то найденное решение максимальное.

Если нет, то заполняем симплексную таблицу 8-го шага и так далее.

Если целевая функция F(X) требует нахождения минимального значения , то критерием оптимальности задачи является неположительность коэффициентов Dj при всех j = 1,2,...n.

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

Легко заметить, что проблемы со сходимостью симплекс-ме­тода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения от­ношения

будут достигнуты для нескольких строк таблицы Т (q) одновре­менно. Тогда на следующей итерации столбец b(β(q+1)) будет со­держать нулевые элементы.

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

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

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

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

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. Привести к симметричному виду задачу линейного программирования