Введение
Линейное программированиенаука о методах исследования и отыскания экстремальных значений линейнойфункции, на параметры которой наложены линейные ограничения.
Методы решения задачлинейного программирования относятся к вычислительной математике. С ростоммощности компьютеров необходимость применения изощренных методов вычисления снижается,поскольку во многих случаях время счета перестает быть лимитирующим фактором,поскольку весьма мало (доли секунд). Можно выделить лишь три таких метода.
1. Простой перебор. Возьмем некоторый многомерныйпараллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как егопостроить? Например, если имеется ограничение типа 2Х1 + 5Х2 ≤10, то, очевидно, 0 ≤ Х1 ≤ 10/2 = 5 и 0 ≤ Х2 ≤10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейтик ограничениям на отдельные переменные. Остается взять максимальные границы покаждой переменной. Если многогранник, задаваемый ограничениями, неограничен,как было в задаче о диете, можно похожим, но несколько более сложным образомвыделить его «обращенную» к началу координат часть, содержащуюрешение, и заключить ее в многомерный параллелепипед.
Проведем перебор точекпараллелепипеда с шагом 1/10n последовательно при n=2,3,…, вычисляязначения целевой функции и проверяя наличие ограничений. Из всех точек,удовлетворяющих ограничениям, возьмем ту, в которой целевая функциямаксимальна. Решение найдено!
2. Направленный перебор. Начнемс точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будемпоследовательно (или случайно — т.н. метод случайного поиска) менять еекоординаты на определенную величину ∆, каждый раз в точку с более высокимзначением целевой функции. Если выйдем на плоскость ограничения, будемдвигаться по ней (находя одну из координат по уравнению ограничения). Затемдвижение по ребру (когда два ограничения-неравенства переходят в равенства)…Остановка — в вершине линейного многогранника. Решение найдено! (Более строговыражаясь, найдено с точностью до ∆; если необходимо, в окрестностинайденного решения проводим направленный перебор с шагом ∆/2, ∆/4и т.д.)
3. Симплекс-метод. Этот один из первыхспециализированных методов оптимизации, нацеленный на решение задач линейногопрограммирования, в то время как методы простого и направленного перебора могутбыть применены для решения практически любой задачи оптимизации. Он былпредложен американцем Г. Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором накаждом шаге значение целевой функции улучшается до тех пор, пока не будетдостигнут оптимум.
Такой многогранникограничений можно назвать функцией, которая для задачи линейногопрограммирования является целевой, а ограничения, записываемые в виде линейныхуравнений или неравенств, называются системой ограничений.
Общей задачей длялинейного программирования является нахождение неотрицательного решения системылинейных ограничений, которое оптимизирует линейную целевую функцию:
f(x1,x2,…,xn)=c1x1+c2x2+…+cnxn→max (min)
Выделяют две формы задачлинейного программирования:
1. стандартная форма
2. каноническая форма
Планом называется вектор x=(x1,x2,…,xn) Rn, удовлетворяющий условиям (1)-(3).Множество всех допустимых решений задачи будем обозначать через X.допустимое решение x X, при котором целевая функция достигает наибольшего (max) или наименьшего значения (min), называется оптимальным решениемзадачи линейного программирования. Базисное неотрицательное решение x=(x1,x2,…,xr,0,…,0), где r- ранг системы ограничений,называется опорным решением.
1. Обыкновенные имодифицированные жордановы исключения
Для рассмотрения сутисимплекс метода в задачах линейного программирования необходимо остановиться напонятии «обыкновенные и модифицированные жордановы исключения».
Пусть дана система из m линейных функций y1,…,ymот nнеизвестных x1,x2,…,xn: yi=∑ aij xj(1.1), где aij– постоянные величины( i =1,m; j =1,n).
Представим систему (1.1) вформе таблицы 1.3, которую в дальнейшем будем называть жордановой.
Таблица 1.3
x1 … xj … xs … xn
y1=
…
yi=
…
yj=
…
ym=
a11 … a1j … a1s … a1n
………………………………….
ai1 … aij … ais … ain
…………………………………
ak1 … akj … aks … akn
…………………………………
am1 … amj … ams … amn
Перейдём к обычной записисистемы путём умножения элементов aij i-й строки на соответствующие неизвестные xj, стоящие в верхней заглавной строке,затем полученные произведения складываем и приравниваем к yi .
Выбираем из (1.1) k-е уравнение yk=∑akj xj(1.2), и, положим, коэффициент при xs отличен от нуля. Выразим xs:
xs=∑
Такая операция называетсяшагом жорданова исключения произведенным над табл.1.3 с разрешающим элементом aksс k-й разрешающей строкой и s-м разрешающим столбцом. Далее для выяснения как изменятсяостальные элементы в табл. 1.3. подставляем значение xsиз в остальные равенства системы
Система запишется в виде
yi=∑ ( i=1,…,m)
Преобразованную систему переписываемв форме жордановой таблицы (табл. 1.4)
Таблица 1.4
x1 … yк … xn
y1=
…
xs =
…
ym=
b11 … … b1n
………………………
… …
………………………
bm1 … … bmn
Сопоставляя табл. 1.3 и1.4, необходимо обратить внимание, что шаг обыкновенного жорданова исключения сразрешающим элементом aksпереводит одну таблицу в другую по схеме из четырех правил:
1. разрешающий элемент (РЭ) заменяетсяобратной величиной;
2. остальные элементы разрешающей строкиделятся на РЭ и меняют знаки;
3. остальные элементы разрешающегостолбца делятся на РЭ;
4. прочие элементы вычисляются поформуле (1.5).
На практике удобнопользоваться правилом прямоугольника:
…………………….………
………aij ……… ais………
……………………………
……… akj……… aks………
……………………………
Тогда из формулынепосредственно следует, что преобразованный элемент bij равен разности произведенийэлементов, расположенных на главной и побочной диагоналях, деленной на РЭ.
2. Идея симплекс метода
Симплекс-метод,называемый также методом улучшения плана, является одним из универсальныхметодов решения задач линейного программирования.
Если задача линейногопрограммирования записана в каноническом виде
f=∑ cixj (max)
∑ aijxj = ai0 (i=1,…,m)
xj>0 (j= 1,…,n)
Тогда, если оптимальныйплан задачи существует, то он совпадает по крайней мере с одним из опорныхрешений системы. Это опорное решение отыскивается симплекс-методом в процессеупорядоченного перебора только опорных решений системы.В связи с этимсимплекс-метод и называют методом последовательного улучшения плана. Поискначального опорного плана составляет первый этап симплекс-метода. На второмэтапе среди опорных планов отыскивается оптимальный.
Рассмотрим суть симплекс-метода.Если в системе m, выразим их через свободныепеременные xm+1,…,xn
xi= bi0 -∑ bij xm+1 (i=1,..,m)
Подставив значения xi в целевую функцию, получаем:
f=b00 — ∑ b0j xm+j
Значения базисныхпеременных xiи целевой функции f полностью определяются значениямисвободных переменных xm+j.
Положим, что все bi0>0. Тогда план x0=(b10;…;bm0;0…;0), полученный при нулевых значениях свободныхпеременных xm+j, будет невырожденным опорным, а отвечающее емузначение функции f равно, как видноb00.
Опорный план x0соответствует базису Б0={x1;…;xm}.Для получения другого опорного плана преобразовывают базис Б0 вновый базис Б1, удаляя из Б0 одну переменную и вводявместо нее другую из группы свободных. При этом в базисе Б1опорному плану x1 соответствует значение f(x1), не меньшееf(x0). Действуя таким образом,переходят к близкому к оптимальному плану. Ввиду того что опорных планов неболее С, через конечное число шагов либо приходят к оптимальному плану, либоустанавливают, что задача неразрешима.
линейноепрограммирование симплекс задача
3. Построение начальногоопорного решения
Решение задачлинейного программирования вручную наиболее рационально можно выполнять именнов табличной форме. В таблицу вписывают систему ограничительных уравнений ицелевую функцию в виде выражений, разрешенных относите льно начального базиса Бо={х1; ...; хт} (табл. 2.). Левый столбец занимают базисныепеременные и целевая функция, а верхнюю строку — свободные переменные. Нижнюю строку,в которую вписаны коэффициенты целевой функции f, называют f-строкой или строкой целевой функции… За столбцом базисных переменных следуетстолбец свободных членов. Иногда f-строкупомещают сразу же за заглавной строкой, а столбец свободных членов в конце;таблицы. Таблицы описанного вида называются симплексными.
Таблица2базисные переменные 1
свободные переменные
-xm+1 … -xm+s… -xn
x1=
…
xk=
…
xm=
b10
…
bk0
…
bm0
b11 … b1s … b1,n-m
……………………………………
bk1 … bks … bk,n-m
……………………………………
bm1 … bms … bm,n-m f=
b00
b01 … b0s … b0,n-m
Используютсяи другие формы симплексных таблиц, но принятая нами форма является наиболеекомпактной и наглядной. В ней содержится вся необходимая информация о ходерешения задачи. Если, как предполагалось выше, все bi0>0, то при нулевых значениях верхних (свободных)переменных столбец свободных членов дает значения базисных переменных опорногоплана xо= (b10;…;bm0;0;… 0) и соответствующее значение b00 целевой функции: f(х0) = b00.
От табличной записи легкоперейти к обычной записи уравнений. Для этого надо умножить элементы bkj k-й строкина соответствующие переменные, стоящие в заглавной строке (-xm+i), полученные произведения сложить и сумму приравнять xkТогда
bko*1 + bk1 (—xm+l)+… +bks{—xm+s)+… + bk,n-m(—xn)=xk или xi = bi0-∑ bij xm+1 .
4. Критерии оптимальности
Рассмотримпоследовательность решения задач линейного программирования симплекс-методом иизложим ее применительно к задаче максимизации.
1. Поусловию задачи составляется ее математическая модель.
2. Составленнаямодель преобразовывается к канонической форме. При этом может выделиться базисс начальным опорным планом.
3. Каноническаямодель задачи записывается в форме симплекс-таблицы так, чтобы все свободныечлены были неотрицательными. Если начальный опорный план выделен, то переходятк пункту 5.
4. Находятначальный опорный план, производя симплексные преобразования с положительными разрешающимиэлементами, отвечающими минимальным симплексным отношениям, и не принимая вовнимание знаки элементов f-строки.Если в ходе преобразований встретится 0-строка, все элементы которой, кромесвободного члена, нули, то система ограничительных уравнений задачинесовместна. Если же встретится 0-строка, в которой, кроме свободного члена,других положительных элементов нет, то система ограничительных уравнений неимеет неотрицательных решений.
5.Найденный начальный опорный план исследуется на оптимальность:
а) еслив f-строке нет отрицательных элементов (несчитая свободного члена), то план оптимален. Если при этом нет и нулевых, тооптимальный план единственный; если же есть хотя бы один нулевой, тооптимальных планов бесконечное множество;
б) еслив f-строке есть хотя бы одинотрицательный элемент, которому соответствует столбец неположительныхэлементов, то f→ ;
в)если в f-строке есть хотя бы одинотрицательный элемент, а в его столбце есть хотя бы один положительный, томожно перейти к новому опорному плану, более близкому к оптимальному. Для этогоуказанный столбец надо назначить разрешающим, по минимальному симплексному отношениюнайти разрешающую строку и выполнить симплексное преобразование. Полученныйопорный план вновь исследовать на оптимальность. Описанный процесс повторяетсядо получения оптимального плана либо до установления неразрешимости задачи.
Важнозаметить, что поскольку min f= — max( —f), задачу минимизации f можно формально заменить задачей максимизации функции (—f). Но можно этого и не делать.Признаком оптимальности опорного плана задачи минимизации является отсутствиеположительных элементов в f-строкесимплекс-таблицы, содержащей опорный план. В остальном вычислительная процедуране меняется.
Впункте 3 алгоритма предполагается, что все элементы столбца свободных членовнеотрицательны. Это требование не обязательно, но если оно выполнено, то всепоследующие симплексные преобразования производятся только с положительнымиразрешающими элементами, что удобно при расчетах. Если в столбце свободныхчленов есть отрицательные числа, то разрешающий элемент выбирают следующимобразом:
1) просматриваютстроку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либоотрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагая,что ограничения задачи совместны);
2) составляютотношения элементов столбца свободных членов к соответствующим элементамразрешающего столбца, имеющим одинаковые знаки (симплексные отношения);
3) изсимплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пустьею будет, например, р -строка;
4) напересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающимоказался элемент t-строки, то послесимплексного преобразования свободный член этой строки станет положительным. Впротивном случае на следующем шаге вновь обращаются к t-строке. Если задача разрешима, то через некоторое числошагов в столбце свободных членов не останется отрицательных элементов. Если вформу задачи линейного программирования облечена некоторая реальнаяпроизводственная ситуация, то дополнительные переменные, которые приходитсявводить в модель в процессе преобразования ее к канонической форме, всегдаимеют определенный экономический смысл.
4.1 Признак оптимальностиопорного плана
Если в симплекс-таблице,содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этотопорный план является оптимальным… Пусть в f-строкетабл. 2.b0j> (i=1, ..., n m). Вопорном плане х0, содержащемся в этой таблице, значения всехсвободных переменных xm+j равнынулю и f(х0) =b00. Если же увеличивать какую-либо из свободных переменных xm+j, то,как видно из равенства (2.5), в силу неотрицательности b0j значениеf(х) начнет уменьшаться.Следовательно, при xо функция f(х) достигает наибольшей величины, а значит, х0действительно является оптимальным опорным планом.
4.2 Возможность переходот одного опорного плана к другому
Как уже говорилось выше,суть симплекс-метода в процессе доказательства следующего признака: если в f-строке симплекс-таблицы, содержащейнекоторый опорный план, есть хотя бы один отрицательный элемент (не считаясвободного члена), которому соответствует столбец с хотя бы одним положительнымэлементом, то можно, преобразовав базис, перейти к другому опорному плану сбольшим значением целевой функции.
Докажемэтот признак. Установим правила выбора переменных для такого преобразованияначального базиса Бо с опорным планом х0в новый базис Б1с опорным планом х1 при котором; значение функции f увеличивается, т. е. f(xi)>f(x0). Тогда по правилу пересчетаэлементов из симплекс-таблицы преобразуем к новому базису, что позволит найтикомпоненты нового опорного плана.
Допустим,что в табл. 2.1, например, b0sxm+s. Из этого равенства видно, что при увеличении xm+sзначение f тоже возрастает. Таким образом, при указанных в признаке условияхдействительно есть возможность увеличить f(x), переходя кпланам, в которых xm+s принимает положительные значения, авсе остальные компоненты xm+jпо-прежнему равны нулю. Покажем, что среди таких планов существует и опорный.Тем самым будет найден путь направленного преобразования базиса Бо вновый базис Б1. В самом деле, если переменная xm+s принимает положительное значение в некотором опорномплане, значит, она является в нем базисной компонентой (в опорном плане xо она была свободной компонентой и равнялась нулю).Поэтому прежний базис следует преобразовать за счет включения в него переменнойxm+s. Но здесь предстоит решить два вопроса:
1)какую из переменных следует вывести из прежнего базиса, чтобы освободить местодля переменной xm+s;
2)какое значение должна принимать новая базисная переменная xm+s в новом опорном плане.
Длярешения поставленных вопросов допустим, что в равенствах (2.4) все xm+j, кроме xm+s,равны нулю. Тогда
xi = bio-bisxm+s (i=l, ..., m)
Изэтих равенств видно, что с возрастанием xm+s значения тех базисных переменных хi для которых коэффициенты bis 0. С увеличением xm+sзначения этих переменных станут уменьшаться, инаступит момент, после которого они будут принимать отрицательные значения иперестанет выполняться условие (2.3). Этого допустить нельзя. Поэтому выясним,до какого предельного значения можно увеличивать xm+s, не нарушая условия неотрицательности базисныхпеременных. С этой целью выпишем из системы (2.6) те равенства, в которых bis>0. Допустим, что это касаетсяравенств с номерами i=d,…,k,…,p:
xd=bdo— bds xm+s,
…………………..
xk=bk0 — bks xm+s,
………………….
xp=bp0 – bps xm+s.
Базисныепеременные хd, ..., xk, ..., xp будут оставаться неотрицательными дотех пор, пока xm+s удовлетворяет системе неравенств
bdo — bds xm+s>0, xm+s
……………… ………………
bk0 — bks xm +s >0 или xm+s
……………… ………………
bp0 – bps xm+s>0 xm+s
т. е. при xm+s
Пустьнаименьшая из дробей bio/bis соответствует i = k, т.е.
min { bio/bis }= bk0/bks.
Тогдаможно сказать, что пока xm+sне превышает величины bk0/bks, т. е. xm+sположить равной bk0/bks >0, то переменная хk станет равной пулю: xk= bk0— bks bko/bks =0, и тем самым будет произведенопреобразование базиса Бо= {х1; ...; xk; ...; хm} в новый базис, при котором переменная xm+sиз группы свободных переходит в базисные, а переменнаяхk занимает место xm+sв группе свободных. При этом все остальные свободныепеременные по-прежнему равны нулю, а остальные базисные переменные по-прежнемуположительны. Следовательно, базисный план х1 в новом базисе Б1={х1;...; xm+s; ...; xm} будет иметь m положительных компонент и m-n нулевых. В плане x1 некоторыебазисные переменные могут принять нулевые значения в двух случаях:
1)когда в плане х0имеются базисные переменные, равные нулю;
2)когда наименьшая из дробей bio/bis будетсоответствовать двум или нескольким номерам i.В нашем же случае она соответствует только i = k.
Переменная,подлежащая включению в базис, определяется отрицательным элементом f-строки. Из равенства f =boo– bos xm+s ясно, что при b0s0, значение f(х) зависит от абсолютной величины коэффициента b0s: чем больше |b0s|, тем большее значение получит f(х) в новом базисе. Но из этого равенства видно также, чтозначение целевой функции в новом базисе зависит и от величины, принимаемойновой базисной переменной xm+s.Будем выбирать переменную, вводимую в базис, ориентируясь лишь на отрицательныеэлементы f-строки. Поэтому, когда в f-строке несколько отрицательныхэлементов, в базис будем вводить переменную xm+j, соответствующую отрицательному элементу с наибольшейабсолютной величиной. Столбец коэффициентов при переменной, включаемой в базис,называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (иливыбирая разрешающий столбец) по отрицательному элементу f-строки, мы обеспечиваем возрастаниефункции f.
Немногосложней определяется переменная, подлежащая исключению из базиса. Для этогосоставляют отношения свободных членов к положительным элементам разрешающегостолбца (такие отношения называют симплексными) и находят среди них наименьшее,которое и определяет строку (разрешающую), содержащую исключаемую переменную.Выбор переменной, исключаемой из базиса (или выбор разрешающей строки), поминимальному симплексному отношению гарантирует положительность базисныхкомпонент в новом опорном плане.
Итак,мы доказали, что при указанных в признаке условиях действительно можно перейтиот одного опорного плана к другому с большим значением целевой функции f(х).
Отметим,что нам уже известно значение новой базисной переменной xm+sв новом опорном плане: оно равно bko/bks. Что же касается численных значенийостальных базисных переменных в новом опорном плане и соответствующего значенияf(х), то их можно найти лишь послетого, как измененная система базисных переменных х1;..., xm+s; ..., хm будет выражена через измененную систему свободных переменныхxm+1,…,xk,…, хn. Для этого установим; правила, по которымосуществляется преобразование условий задачи от одного базиса к другому.
Коэффициентbks= 0 при xm+s в этом уравнении называют разрешающим элементом. Вравенстве (2.7) новая базисная переменная xm+sвыражена через свободные переменные, среди которыхнаходится теперь и бывшая базисная переменная хk. Таким образом, переменные xm+s и xkпоменялись ролями.
Аналогичновыразим через новый набор свободных переменных и остальные базисные переменные.С этой целью значение xm+sизподставим в остальные равенств (обозначим f через x0, тогда равенство будет входить всистему при i= 0)
Приведениесистемы к новому базису называется симплексным преобразованием. Еслисимплексное преобразование рассматривать как формальную алгебраическуюоперацию, то можно заметить, что в результате этой операции происходитперераспределение ролей между двумя переменными, входящими в некоторую системулинейных функций: одна переменная из зависимых переходит в независимые, адругая, наоборот, — из независимых в зависимые. Такая операция известна валгебре под названием шага жорданова исключения.
4.3 Признакнеограниченности целевой функции на множестве планов
Если в f-строке симплекс-таблицы, содержащейнекоторый опорный план, есть хотя бы один отрицательный элемент, которомусоответствует столбец неположительных элементов, то целевая функциянеограничена на множестве планов, т. е. f→ .
Докажемэто утверждение. Пусть в табл. 2, например, b0s, равными нулю, получим
xi = bio — bis xm+s (i=1,..., m)
f=boo — b0s xm+s.
Изравенств видно, что переменную xm+sможнопроизвольно увеличивать, не опасаясь нарушить условие неотрицательности базисныхпеременных xi ибо bi0>0, ( — bis)>0, а значит, и xi>0 при любых xm+s>0.В то же время, как видно, где (- b0s)>0, значение f(х) будет монотонно возрастать, и если
xm+.s→, то и f→ .
4.4 Признак бесконечностимножества оптимальных планов
Если в f-строке симплекс-таблицы, содержащейоптимальный план, есть хотя бы один нулевой элемент (не считая свободногочлена), то задача линейного программирования имеет бесконечное множествооптимальных планов.
Докажемэто утверждение. Допустим, что содержащийся в табл. 2 опорный план являетсяоптимальным. Обозначим его через х1*. Пусть при этом элемент bosf-строки равен нулю, а все остальныеэлементы этой строки положительны. Тогда, подвергнув табл. 2 симплексномупреобразованию с s-м разрешающимстолбцом, мы придем к другой таблице с новым опорным планом, который такжебудет оптимальным, поскольку элементы f-строки не изменились (нулевой элемент bos f-строки расположен в разрешающем столбце). Обозначим этотновый опорный оптимальный план через х2*. В соответствии с основнойтеоремой линейного программирования утверждаем, что любой план х*, являющийсявыпуклой линейной комбинацией планов х1* и х2*, тожебудет оптимальным.
Еслив f-строке будет t(t
x*=λ1x1*+…+λt+1xt+1*, где λl>0 (l=1,…,t+1) иλ1 +…+λt+1=1
Всемножество оптимальных планов можно записать в виде
х*=λх1*+ (1- λ) х2*
4.5Понятие о проблеме вырождения. Зацикливание
Рассматриваяпреобразование одного базиса в другой, мы предполагали, что среди симплексныхотношений имеется только одно наименьшее, и поэтому вопрос о выборе переменной,исключаемой из базиса, решался однозначно. Но если допустить, что в разрешающемстолбце min bi0/bis достигается для нескольких индексов, например для i = l и i = t, т. е.
blobts = btobls
иразрешающей выбрана l-я строка. Тогдав новом опорном плане базисная переменная xt в соответствии с формулой (2.8) будет равна
b'to=(btobls — blobts): bis
Отсюдаполучаем xt = b't0= 0. Такимобразом, новый опорный план будет вырожденным. Задача линейногопрограммирования, имеющая хотя бы один вырожденный опорный план, называетсявырожденной.
Если прирешении вырожденной задачи на очередном шаге симплексных преобразованийразрешающей окажется строка, в которой свободный план равен нулю, то нулю будетравна и новая базисная компонента очередного опорного плана, тогда как значенияостальных базисных компонент и целевой функции останутся прежними. Как правило,после нескольких шагов, сопровождающихся постоянством значения f, приходят все же к опорному плану с большим,чем прежде, значением f, ирешение задачи благополучно заканчивается. Вместе с тем не исключается случай,когда после нескольких итераций получают уже встречавшийся базис, обнаруживаетсяявление зацикливания в схеме расчетов. Одно из правил, позволяющихпредотвратить это нежелательное явление, формулируется так: если в процессесимплексных преобразований появляется несколько минимальных симплексныхотношений, то выбирают ту строку, для которой будет наименьшим отношениеэлементов первого столбца к разрешающему. Если при этом снова оказываетсянесколько минимальных отношений, то составляются отношения элементов следующего(второго) столбца, и так до тех пор, пока разрешающая строка не определитсяоднозначно.
Итак,если задача линейного программирования вырожденная, то зацикливание возможно.Однако и теоретические исследования и накопившийся опыт решения прикладныхзадач показывают, что зацикливание может возникнуть лишь при весьма маловероятномсочетании различных особых условий. Известны лишь несколько специальносоставленных примеров, в процессе решения которых возникает зацикливание.
Заключение
Анализируявсё вышеизложенное, мы приходим к выводу о том, что при решении задач линейногопрограммирования «вручную» оптимально использовать симплекс – метод. Посколькуон позволяет при верном составлении опорного плана решения быстро найтирезультат. Для этого необходимо знать последовательность шагов при этом методеи уметь производить различные преобразования в симплекс- таблице.
Список литературы
1 Ашманов С.А., Линейноепрограммирование. М.: Наука 1981.
2. Кузнецов А.В., Холод Н.И.,Математическое программирование. Мн.: Высшая школа 1984
3. Кузнецов А.В., Холод Н.И.,Костевич Л.С., Руководство к решению задач по математическому программированию.Мн.: 2001
4. Кузнецов А.В., Холод Н.И., НовиковаТ.И. сборник задач по математическому программированию. Мн.: Высшая школа 1994
5. Кузнецов А.В., Холод Н.И., СоковичВ.А.., Высшая математика. Математическое программирование. Мн.: Высшая школа1987