В общем случае задача линейного программирования записывается так, что ограничениями являются как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольно изменяющимися. В том случае, когда все ограничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической. Она может быть представлена в координатной, векторной или матричной записи.
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. Привести к симметричному виду задачу линейного программирования
задачи линейного программирования
2.1. Определение и формы записи
В случае, когда все ограничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической. Она может быть представлена в координатной, векторной или матричной форме записи.
а) каноническая задача ЛП в координатной форме имеет вид:
,
.
Данную задачу можно записать, используя знак суммирования:
,
,
,
,
.
б) каноническая задача ЛП в векторной форме имеет вид: ,
,
где
;
;
,
;
;
.
в) каноническая задача ЛП в матричной форме имеет вид:
,
,
где
,
,
.
2.2. Приведение общей задачи линейного
программирования к канонической форме
При составлении математических моделей экономических задач ограничения в основном формируются в системы неравенств. Поэтому необходимо уметь переходить от них к системам уравнений. Например, рассмотрим линейное неравенство
и
прибавим к его левой части некоторую
величину
такую, чтобы неравенство превратилось
в равенство.
Неотрицательная
переменная
называется дополнительной переменной.
Следующая теорема даёт основание для
возможности такого преобразования.
Теорема
2.2.1.
Каждому решению
неравенства (2.2.1) соответствует
единственное решениеуравнения (2.2.2) и неравенства
,
и, наоборот, каждому решению уравнения
(2.2.2)с
соответствует решение
неравенства (2.2.1).
Доказательство.
Пусть
решение
неравенства (2.2.1). Тогда.
Возьмём число
.
Ясно, что
.
Подставив в уравнение (2.2.2), получим
Первая часть теоремы доказана.
Пусть теперь
вектор
удовлетворяет уравнению (2.2.2) с
,
т.е..
Отбрасывая в левой части последнего
равенства неотрицательную величину
,
получаем,
и т.д.
Таким образом, доказанная теорема фактически устанавливает возможность приведения всякой задачи ЛП к каноническому виду. Для этого достаточно в каждое ограничение, имеющее вид неравенства, ввести свою дополнительную неотрицательную переменную. Причём, в неравенства вида (1.2.1) эти переменные войдут со знаком « + », а в неравенствах вида (1.2.2) – со знаком « – ». Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому на её значение не влияют.
Замечание.
В дальнейшем мы будем излагать
симплекс-метод для канонической задачи
ЛП при исследовании целевой функции на
минимум. В тех задачах, где требуется
найти максимум
,
достаточно рассмотреть функцию
,
найти её минимальное значение, а затем,
меняя знак на противоположный, определить
искомое максимальное значение
.
3. Графический метод решения задач
линейного программирования
3.1. Общие понятия, примеры
В
тех случаях, когда в задаче ЛП лишь две
переменные, можно использовать для
решения графический метод. Пусть
требуется найти максимальное (минимальное) значение функции
при ограничениях
(3.1.1)
Данный метод
основывается на возможности графического
изображения области допустимых решений
задачи, т.е. удовлетворяющих системе
(3.1.1), и нахождения среди них оптимального
решения. Область допустимых решений
задачи строится как пересечение (общая
часть) областей решений каждого из
заданных ограничений (3.1.1). Каждое из
них определяет полуплоскость с границей
,
.
Для того, чтобы определить, какая из
двух полуплоскостей является областью
решений, достаточно координаты какой-либо
точки, не лежащей на прямой, подставить
в неравенство: если оно удовлетворяется,
то областью решений является полуплоскость,
содержащая данную точку, если же
неравенство не удовлетворяется, то
областью решений является полуплоскость,
не содержащая данную точку.
Пересечение этих полуплоскостей образует некоторую область, называемую многоугольником решений, который является выпуклым множеством. (Допустим, что система ограничений совместна, а многоугольник её решений ограничен.) Для нахождения среди допустимых решений оптимального используются линии уровня и опорные прямые.
Линией
уровня
называется прямая, на которой
целевая функция
принимает постоянное значение. Уравнение
линии уровня имеет вид
,
где
.
Все линии уровня параллельны между
собой. Их нормаль
.
Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений, по отношению к которой эта область находится в одной из полуплоскостей (рис. 1).
Значения
возрастают в направлении вектора
.
Поэтому необходимо передвигать линию
уровня
в направлении этого вектора параллельно
самой себе до опорной прямойL
1
в задаче на максимум и в противоположном
направлении – в задаче на минимум (до
опорной прямойL
2).
Приведём
решение примера 1.1. Напомним, что нужно
найти максимум функции
при ограничениях
Решение.
Строим область допустимых решений.
Нумеруем ограничения задачи. В
прямоугольной декартовой системе
координат (рис. 2) строим прямую
,
соответствующую ограничению (1). Находим,
какая из полуплоскостей, на которые эта
прямая делит всю координатную плоскость,
является областью решений неравенства
(1).
Для
этого достаточно координаты какой -
либо точки, не лежащей на прямой,
подставить в неравенство. Так как прямая
не проходит через начало координат,
подставляем
в первое ограничение.
Получим строгое неравенство
.
Следовательно, точка
лежит в полуплоскости решений. Аналогично
строим прямую
и область решений ограничения (2). Находим
общую часть полуплоскостей решений,
учитывая ограничения (3). Полученную
область допустимых решений выделим на
рис.2 тёмным цветом.
Строим
линию уровня
и вектор
,
который указывает направление возрастания
функции
и
перпендикулярен прямой
.
Линию уровня
перемещаем параллельно самой себе в
направлении
до опорной прямой. Получим, что максимума
целевая функция достигнет в точке
точке
пересечения прямых
и
.
Решая систему из уравнений этих прямых
,
получим координаты точки
.
Следовательно,,
а
,
оптимальное
решение.
Пример
3.1. Найти минимум функции
при системе ограничений
Решение.
Строим область допустимых решений
(см. рис.3), вектор
и одну из линий уровня
.
Перемещаем линию уровня в направлении,
противоположном
,
так как решается задача на отыскание
минимума функции. Опорная прямая проходит
в этом случае через точку А (рис.3),
координаты которой найдём из решения
системы
Итак,
.
Вычисляем.
Замечание.
В действительности от вида области
допустимых решений и целевой функции
задача ЛП может иметь единственное
решение, бесконечное множество решений
или не иметь ни одного решения.
Пример
3.2. Найти минимум функции
при ограничениях
Решение.
Строим область допустимых решений,
нормаль линий уровня
и одну из линий уровня
,
имеющую общие точки с этой областью.
Перемещаем линию уровня
в направлении, противоположном направлению
нормали
,
так как решается задача на отыскание
минимума функции. Нормаль линий уровня
и нормаль граничной прямой
,
в направлении которой перемещаются
линии уровня, параллельны, так как их
координаты пропорциональны
.
Следовательно, опорная прямая совпадает
с граничной прямой
области допустимых решений и проходит
через две угловые точки этой области
и
(рис.4).
Задача имеет
бесконечное множество оптимальных
решений, являющихся точками отрезка
.
Эти точки
,
находим, решая соответствующие системы
уравнений:
;
;
,
;
,
;
;
.
Вычисляем .
Ответ:
при
,
.
Пример 3.3. Решить задачу линейного программирования
Решение.
Строим область допустимых решений,
нормаль
и одну из линий уровня. В данной задаче
необходимо найти максимум целевой
функции, поэтому линию уровня
перемещаем в направлении нормали. Ввиду
того, что в этом направлении область
допустимых решений не ограничена, линия
уровня уходит в бесконечность (рис.5).
Задача не имеет решения вследствие неограниченности целевой функции.
Ответ:
.
Аналитическим методом решения задачи линейного программирования является симплексный метод. Для его применения задачи ЛП, представленные различным образом, должны быть приведены к канонической форме. Задача линейного программирования, записанная в виде (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.
Задачи МП
Общей ЗЛП называют <,=,>=}bi (i=1,n) (2) при условии xj>
Симметрической < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Канонической смешенной .
min f(x) = -max(-f(x))
<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>
Геометрическая интерпретация целевой функции и ограничения ЗЛП. Геометрическая формулировка ЗЛП.
Пусть дана задача f=c1x1+c2x2-max (1)
a11x1+a12x2<=b1 }
am1x1+am2x2<=bm}
x1>=0, x2>=0 (3)
План задачи (х1,х2) – точка на плоскости. Каждое неравенство с-мы 2 предст. собой полуплоскость. Полуплоскость –выпуклое множество. Выпуклым наз-ся множество в которым точки отрезка соединяющие (х1 и х2) принадлежащие этому множеству то же принадлежат множеству. С-ма 2 представляет собой пересечение полуплоскостей. При пересечении могут получиться:
1)выпуклая многоугольная замкнутая область.
2) выпуклая открытая многоугольная область
3) единственная точка
4) пустое множество
5) луч и отрезок
Геометрическая интерпретация целевой функции: ф-ция 1 представляет собой семейство параллельных прямых, которые наз-ют линиями уровня(линиями постоянного значения целевой функции). Частные производные функции по х1 и х2 показывают скорость возрастания целевой функции вдоль координат осей. Вектор-градиент показывает направление найскорейшего возрастания целевой функции.Для задачи 1-3 вектор-градиент = (с1;с2) Выходит из точки (0,0) и направлен в точку с координатами (с1;с2). Вектор-градиент перпендикулярен линиям уровня. Пересечение полуплоскастей принято наз-ть областью допустимых рещений(ОДР) .
Основная теорема ЛП. Принципиальная схема решения ЗЛП, вытекающая из этой теоремы.
Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника плана. Если целевая функция достигает экстремального значения более чем в одной крайней точке то она достигает одно и то, являющейся их выпуклой линейной комбинацией.же значения в любой точке. При решении ЗЛП в ручную удобно использовать табличную запись.
| БП | СП -Xm+1 -Xm+2 -Xn | |
| х1 | b1o | b11 b12 b1n-m |
| х2 | b2o | b21 b22 b2n-m |
| хm | bm | bm1 bm2 bmn-m |
| f | boo | bo1 bo2 bon-m |
Алгоритм симплекс-метода.
1. привести модель задачи к канонической форме;
2. найти начальный опорный план;
3. записать задачу в симпл. таблицу;
5. перейти к новому опорному плану, к новой симп. таблице. Для того чтобы перейти к новому опорному плану достаточно заменить одну базисную переменную свободной. Переменную, включаемую в базис и соответствующей ей разрешающий столбец определяют по наибольшему по модулю отрицательному элементу f-строки. Переменную, исключающую из базиса и соответствующую ей разрешающую строку определяют по наименьшему симплексному отношению, т.е. отношению элементов единичного столбца к соответствующему элементу разрешающего столбца. Симплексное отношение – величина неотрицательная. На пересечении разрешающей строки и разрешающего столбца расположен разрешающий элемент, относительно которого выполняется симплексное преобразование по след. правилу: 1. элементы разрешающей строки делятся на разрешающий элемент; 2. элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный; 3. остальные элементы таблицы перещитываются по правилу прямоугольника.:
bij bis bkj=(bkj*bis-bij*bks)/bi
Ая теорема двойственности.
если одна из двойственных задач имеет оптим план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* если в исходн. задаче целевая функция неограничена на множестве планов, то в двойственной задаче система ограничений несовместна.
Теорема о ранге матрицы ТЗ.
Ранг матрицы А трансп.задачи на единицу меньше числа уравнений: r(A)=m+n-1.
39. Алгоритм построения начального опорного плана ЗЛП.
Для нахождения начального опорного плана можно предложить следующий алгоритм:
1. записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т.е. выполнялось неравенство аio>=0 (i=1,m). Те уравнения с-мы, в которых свободные члены отрицательны, предварительно умножаются на -1.
| -x1 ….. -xn | ||
| 0= | a1o | a11 …. a1n |
| ….. | ….. | ……………………….. |
| 0= | amo | am1 ….. amn |
| f= | -c1 …. -cn |
Таблицу преобразовывать шагами жордановых исключений, замещая нули в левом столбце соответствующими х. При этом на каждом шаге разрешающим может быть выбран
любой столбец, содержащий хотя бы один положительный элемент. Разрешающая строка определяется по наименьшему из отношений свободных членов к соответствующем положительным элементам разрешающего столбца. Если в процессе исключений встретится 0-строка, все элементы которой- нули, а свободный член отличен от нуля, то с-ма ограничительных уравнений решений не имеет. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то с-ма ограничительных уравнений не имеет неотрицательных решений Если с-ма ограничительных уравнений совместна
, то через некоторое число шагов все нули в левом столбце будут замещены х и тем самым получен некоторый базис, а следовательно, и отвечающий ему опорный план.
40. Алгоритм построения оптимального опорного плана ЗЛП.
Начальный опорный план Хо исследуется на оптимальность.
Если в f-строке нет отрицательных элементов (не считая свободного члена), -план оптимален. Если в f- строке нет также и нулевых элементов, то оптимальный план единственный; если же среди элементов есть хотя бы один нулевой, то оптимальных планов бесконечное множество. Если в f-строке есть хотя бы один отрицательный элемент, а в соответствующем ему столбце нет положительных, то целевая функция не ограничена в допустимой области. Задача не разрешима. Если в f- строке есть хотя бы один отрицательный элемент, а в каждом столбце с таким элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отриц-ом элементом в f-строке берут за разрешающий ; опред-ют по минимальному симплексному отношению разрешающую строку и делают шаг жорданова исключения. Полученный опорный план вновь исследуется на оптимальность. Это повторяется до тех пор, пока не будет найден оптимальный опорный план либо установлена неразрешимость задачи.
Алгоритм метода Гомори.
1.Симплекс-методом находят оптимальный план задачи. Если все компоненты оптимального плана целые, то он –оптимальный. В противном случае переходят к пункту 2
2.Среди нецелых компонент следует выбрать ту, у которой дробная часть является наибольшей и по соответствующей этой строке симплексной таблицы сформулировать правильное отсечение по формуле
(n-m,s=1)∑ {αkm+1}Xm+1≥{βk}
3.Сформулированное неравенство преобразовать в эквивалентное нулевое равенство и включить в симплексную таблицу с нецелочисленным оптимальным планом
4.Полученную расширенную задачу решают симплекс-методом. Если полученный план не является целочисленным нова переходят к пункту 2.
Если в процессе решения появится строка с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В таком случае и исходная задача неразрешима в целых числах.Метод Гомори имеет ограниченое применение. С его помощью целесообразно решать небольшие задачи, т.к. число интераций может быть очень большим.
Различные формы записи ЗЛП (общая, каноническая, симметрическая)
Задачи МП : определение оптимального плана, опред-е оптимального объема выпуска продукции, опред-е оптим-го сочитания посевов с/хоз-ых культур, формир-е оптим-го пакета активов, максимиз-щий прибыль банка и т.д.
Общей ЗЛП называют задачу максимизации (минимизации) линейной функции f=Σcj*xj-max(min) (1) при линейных ограничениях ∑aij *xj{=<,=,>=}bi (i=1,n) (2) при условии xj>=0(j=1,n1), xj-произвольное (j=n1+1,n)(3) где cj,aij, bi-постоянные числа.
Симметрической формой записи ЗЛП наз-ся задача максимизации функции (1) при линейных ограничениях в неравенствах со знаком < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > либо = и неотрицательных переменных. Канонической формой записи ЗЛП наз-ся задача максимальной функции (1) при линейных ограничениях равенствах и неотрицательных переменных. Любая другая форма называется смешенной .
min f(x) = -max(-f(x))
Преобразование нерав-ва в уравнение и наоборот осущ-ся на основе Леммы: всякому решению х1…хn нерав-ва a1x1+…+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) и наоборот. Всякому решению x1…xn,xn+1 уравнения 6 и неравенства 7 соответствует решение x1…xn неравенства 5.
Чтобы от зад сим формы перейти к зад канонич вида, необходимо ввести балансовые (выравнивающие) переменные. Это основано на теореме о неравенстве: любое нерав-во можно представить в виде ур-я или простейшего нерав-ва.
канонической форме , если требуется максимизировать целевую функцию, все ограничения системы – уравнения и на все переменные наложено условие неотрицательности.
Задача линейного программирования задана в симметричной форме , если требуется максимизировать целевую функцию, все ограничения системы – неравенства «» (или минимизировать целевую функцию, все ограничения системы – неравенства «») и на все переменные наложено условие неотрицательности.
Набор чисел называется допустимым решением (планом) , если он удовлетворяет системе ограничений ЗЛП.
Множество всех допустимых решений называется областью допустимых решений (ОДР).
Допустимое решение , для которого достигается максимальное (минимальное) значение функции, называется оптимальным планом ЗЛП .
Термины «план» и «оптимальный план» возникли из экономических приложений.
Все три формы записи ЗЛП являются эквивалентными в том смысле, что имеются алгоритмы перехода от одной формы к другой. Таким образом, если имеется способ решения задачи в одной из форм, то всегда можно определить оптимальный план задачи, заданной в любой другой форме . Задача в симметричной форме решается графическим методом, а в канонической форме – симплекс–методом.
Рассмотрим алгоритмы перехода от одной формы к другой.
Симметричная каноническая. Переход осуществляется путем добавления в левую часть каждого неравенства дополнительной неотрицательной переменной. Если неравенство было «≤», то балансовая переменная добавляется в левую часть неравенства со знаком «+». Если неравенство было «», то балансовая переменная добавляется в левую часть неравенства со знаком «–». Вводимые новые переменные называются балансовыми . Задачу минимизации функции Z заменяют на задачу максимизации функции (–Z) и используют, что min Z = –max (–Z).
Каноническая симметричная. Для осуществления такого перехода находится общее решение системы уравнений – ограничений, целевая функция выражается через свободные переменные. Далее, воспользовавшись неотрицательностью базисных переменных, можно исключить их из задачи. Симметричная форма задачи будет содержать неравенства, связывающие только свободные переменные, и целевую функцию, зависящую только от свободных переменных. Значения базисных переменных находятся из общего решения исходной системы уравнений.
Общая каноническая. Каждая переменная, на которую не было наложено условие неотрицательности, представляется в виде разности двух новых неотрицательных переменных. Неравенства преобразуются в уравнения путем введения в левую часть каждого неравенства балансовой переменной таким же образом, как это было описано при переходе от симметричной к канонической форме. Задачу минимизации функции Z заменяют на задачу максимизации функции (–Z) таким же образом, как это было описано при переходе от симметричной к канонической форме..
Графический метод решения задачи линейного программирования
Множество точек называется выпуклым , если для любых двух точек множества оно содержит отрезок, их соединяющий.
Пример 1
Следующие множества точек на плоскости являются выпуклыми:
Следующие множества точек на плоскости не являются выпуклыми:
Теорема 1 Пересечение любого количества выпуклых множеств является выпуклым множеством.
Теорема 2 Пусть имеются две произвольные точки и в пространстве R n . Тогда для любой точки отрезка [PQ ] должно выполняться: .где .
Гиперплоскостью в пространстве R n называется множество точек, удовлетворяющее уравнению . Заметим, что в двумерном случае гиперплоскостью является прямая.
Полупространством называется множество точек, удовлетворяющее одному из неравенств или . Гиперплоскость делит точки пространства на два полупространства. В двумерном случае гиперплоскостью является полуплоскость.
Теорема 3 Полупространство является выпуклым множеством.
Следствие Пересечение любого количества полупространств является выпуклым множеством.
Многогранником называется пересечение одного или более полупространств. Многогранник в двумерном случае называется многоугольником.
Пример 2
Следующие множества являются многоугольниками.
Ограниченное множество
Неограниченное множество
Единственная точка
Пустое множество
Точка выпуклого множества называется угловой
, если она не лежит внутри никакого отрезка, соединяющего две другие точки из множества.
Пример 3
Угловыми точками треугольника являются его вершины (их три). Угловыми точками круга являются точки окружности, которая его ограничивает (их бесконечное число).
Угловая точка многогранника называется его вершиной .
Рассмотрим ЗЛП, заданную в симметричной форме.
Теорема 4 Оптимальный план ЗЛП соответствует вершине многогранника решений, определяемого ее системой ограничений.