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

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).

Задача не имеет решения вследствие неограниченности целевой функции.

Ответ:
.

: Задачи линейного программирования (ЗЛП)

1. Линейное программирование

2. Виды задач линейного программирования

3. Формы записи ЗЛП

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

Линейное программирование

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

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

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

Рисунок 1 - Экстремум целевой функции

Математическая модель ЗЛП записывается следующим образом:

max (или min) Z=z(X),(1)

ОДР может быть представлена системой линейных уравнений или неравенств.

Вектор Х=(х 1 , х 2 , .... x п) является вектором управления или управляющим воздействия.

Допустимый план Х, при котором критерий оптимальности Z=z(X) достигает экстремального значения, называется оптимальным и обозначается через X*, экстремальное значение целевой функции -- через Z*=z(X*).

Виды задач линейного программирования

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

Наиболее распространенный тип задач - задача оптимального использования ресурсов. Пусть некоторая производственная единица (цех, предприятие, объединение и т.д.), исходя из конъюнктуры рынка, технических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции, известных под номерами j.

При выпуске продукции предприятие ограничено имеющимися ресурсами, количество которых обозначим m, а вектор ресурсов В = (b 1 , b 2 , ..., b т). Известны также технологические коэффициенты a ij , которые показывают норму расхода i-го ресурса на производство единицы j-ой продукции. Эффективность выпуска единицы j-и продукции характеризуется прибылью p j .

Требуется определить план выпуска продукции Х=(х 1 , х 2 , ..., x п), максимизирующий прибыль предприятия при заданных ресурсах.

Целевая функция выглядит следующим образом

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

Часто ассортимент продукции устанавливается вышестоящей организацией, т. е. его объемы должны быть заключены в некоторых границах D н j и D в j:тогда задается следующее ограничение:

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

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

1) максимум прибыли

2) минимум затрат на производство

3) максимум выпуска в стоимостном выражении (выручки от реализации продукции)

Пример. Предприятие может изготовлять четыре вида продукции 1, 2, 3 и 4. Сбыт любого ее объема обеспечен. Предприятие располагает в течение квартала трудовыми ресурсами в 100 человеко-смен, полуфабрикатами массой 260 кг, станочным оборудованием в 370 станко-смен. Нормы расхода ресурсов и прибыль от единицы каждого вида продукции представлены в табл.1.

Необходимо:

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

б) решить задачу с требованием комплектации, чтобы количество единиц третьей продукции было в 3 раза больше количества единиц первой;

в) выяснить оптимальный ассортимент при дополнительных условиях: первого продукта выпускать не менее 25 единиц, третьего -- не более 30, а второго и четвертого -- в отношении 1:3.

Таблица 1

Исходные данные

Математическая модель задачи:

целевая функция:

max: Z=40x 1 +50x 2 +100x 3 +80x 4

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

а) на трудовые ресурсы:

2,5x 1 +2,5x 2 +2x 3 +1,5x 4 ? 100;

на полуфабрикаты:

4x 1 +10x 2 +4x 3 +6x 4 ? 260;

на станочное оборудование:

8x 1 +7x 2 +4x 3 +10x 4 ? 370;

условие неотрицательности:

б) дополнительное требование комплектации выразится условием

3x 1 =x 3 , т.е 3x 1 x 3 =0;

в) граничные условия и условие комплектации представим так: х 1 ?25,

х 3 ?30, 3*х 2 =х 4 .

Задача о размещении заказов или загрузке взаимозаменяемых групп оборудования . Речь идет о распределения заказов между m (i=1,…, m) предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказов. Требуется составить такой план размещения заказов, при котором задание было бы выполнено, а показатель эффективности достигал экстремального значения.

Сформулируем задачу математически. Пусть на т однородных группах оборудования нужно изготовить п видов продукции. План выпуска каждого вида продукции на определенный период задан набором х j (j=1,2, …п). Мощность каждого вида оборудования ограничена и равна b i . Известна технологическая матрица A=||a ij ||, где a ij --число единиц j-ой продукции, выпускаемой в единицу времени на i-м оборудовании. Матрица С - матрица затрат, где c ij --затраты, связанные с выпуском единицы j-й продукции на i-м оборудовании. Х -- вектор объема выпускаемой продукции.

Модель задачи примет следующий вид:

целевая функция -- минимизация расходов на реализацию всех заказов

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

а) по мощности оборудования

б) на выпуск продукции

в) условие неотрицательности

Данную задачу называют распределительной или задачей распределения.

Если по некоторым видам продукции допускается превышение плана, то ограничение (б) примет вид

В качестве целевой прибыли также можно принять:

а) максимум прибыли

б) минимум затрат станочного времени

Т.к. любая модель содержит упрощающие предпосылки, для корректного применения полученных результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее существенным упрощением в рассмотренных моделях является предположение о прямопропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат a ij . Очевидно, что это допущение далеко не всегда выполняется. Так объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно - в зависимости от изменения программы производства Х. К другим упрощающим предпосылкам относятся предположения о независимости цен j от объемов x j , что справедливо лишь для определенных пределов их изменения. Данные «уязвимые» места важно знать еще и потому, что они указывают принципиальные направления усовершенствования модели.

Формы записи ЗЛП

Существует 3 формы записи ЗЛП:

1) в виде функций

max(или min)Z=,max(или min)Z=,

2) векторная форма

(скалярное произведение векторов)

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

A 1 х 1 +A 2 х 2 +..+A n x n = B

Где векторы

С = (С 1, С 2 .. С n), Х = (Х 1, Х 2 .. Х n), и.

3) матричная форма

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

где С = (с 1 , с 2 ,…с n),

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

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные x j налагаются условия неотрицательности, то она называется задачей линейного программирования в канонической форме или канонической задачей линейного программирования (КЗЛП).

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

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

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

1) если в ограничениях правая часть отрицательная, то следует умножить это ограничение на -1;

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

3) если некоторая переменная xk не имеет ограничений по знаку, то она заменяется в целевой функции и во всех ограничениях разностью между двумя новыми неотрицательными переменными: xk=x * k - xl, где l - сводный индекс, x * k>=, xl>=0.

Рассмотрим пример. Приведем к канонической форме:

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

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

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

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

оптимизационный симплексный линейный программирование

Задачи МП

Общей ЗЛП называют <,=,>=}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.

Чтобы от зад сим формы перейти к зад канонич вида, необходимо ввести балансовые (выравнивающие) переменные. Это основано на теореме о неравенстве: любое нерав-во можно представить в виде ур-я или простейшего нерав-ва.

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

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

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

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

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) переход к новому, "лучшему" опорному плану.

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

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

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