Меню
  Список тем
  Поиск
Полезная информация
  Краткие содержания
  Словари и энциклопедии
  Классическая литература
Заказ книг и дисков по обучению
  Учебники, словари (labirint.ru)
  Учебная литература (Читай-город.ru)
  Учебная литература (book24.ru)
  Учебная литература (Буквоед.ru)
  Технические и естественные науки (labirint.ru)
  Технические и естественные науки (Читай-город.ru)
  Общественные и гуманитарные науки (labirint.ru)
  Общественные и гуманитарные науки (Читай-город.ru)
  Медицина (labirint.ru)
  Медицина (Читай-город.ru)
  Иностранные языки (labirint.ru)
  Иностранные языки (Читай-город.ru)
  Иностранные языки (Буквоед.ru)
  Искусство. Культура (labirint.ru)
  Искусство. Культура (Читай-город.ru)
  Экономика. Бизнес. Право (labirint.ru)
  Экономика. Бизнес. Право (Читай-город.ru)
  Экономика. Бизнес. Право (book24.ru)
  Экономика. Бизнес. Право (Буквоед.ru)
  Эзотерика и религия (labirint.ru)
  Эзотерика и религия (Читай-город.ru)
  Наука, увлечения, домоводство (book24.ru)
  Наука, увлечения, домоводство (Буквоед.ru)
  Для дома, увлечения (labirint.ru)
  Для дома, увлечения (Читай-город.ru)
  Для детей (labirint.ru)
  Для детей (Читай-город.ru)
  Для детей (book24.ru)
  Компакт-диски (labirint.ru)
  Художественная литература (labirint.ru)
  Художественная литература (Читай-город.ru)
  Художественная литература (Book24.ru)
  Художественная литература (Буквоед)
Реклама
Разное
  Отправить сообщение администрации сайта
  Соглашение на обработку персональных данных
Другие наши сайты
Приглашаем посетить
  Толстой (tolstoy-lit.ru)

   

Последовательность решения задач линейного программирования симплекс-методом

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

1. Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х1 + 5Х2 ≤ 10, то, очевидно, 0 ≤ Х1 ≤ 10/2 = 5 и 0 ≤ Х2 ≤ 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек параллелепипеда с шагом 1/10n найдено!

2. Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т. н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т. д.)

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

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

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

f(x1 ,x2 ,…,xn )=c1 x1 +c2 x2 +…+cn xn→ max (min)

1. стандартная форма

2. каноническая форма

Планом называется вектор x=(x1 ,x2 ,…,xn ) Rn , удовлетворяющий условиям (1)-(3). Множество всех допустимых решений задачи будем обозначать через X. допустимое решение xX, при котором целевая функция достигает наибольшего (max) или наименьшего значения (min), называется оптимальным решением задачи линейного программирования. Базисное неотрицательное решение x=(x1 ,x2 ,…,xr ,0,…,0) , где r- ранг системы ограничений, называется опорным решением.


1. Обыкновенные и модифицированные жордановы исключения

Пусть дана система из m линейных функций y1 ,…,ym от n неизвестных x1 ,x2 ,…,xni =∑ aij xjij

Таблица 1. 3

x1 … xjs … xn

y1 =

yi =

yj =

ym =

a11 … a1j … a1s1n

ai1 … aijis … ain

…………………………………

ak1 … ak j … 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

x1 … yкn

y1 =

xs =

ym =

b11 … … b1n

………………………

………………………

bm1 … … bmn

Сопоставляя табл. 1. 3 и 1. 4, необходимо обратить внимание, что шаг обыкновенного жорданова исключения с разрешающим элементом aks переводит одну таблицу в другую по схеме из четырех правил:

2. остальные элементы разрешающей строки делятся на РЭ и меняют знаки;

3. остальные элементы разрешающего столбца делятся на РЭ;

4. прочие элементы вычисляются по формуле (1. 5).

На практике удобно пользоваться правилом прямоугольника:

………aijis ………

…….. akj ……… aks ………

……………………………


Тогда из формулы непосредственно следует, что преобразованный элемент bij


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

∑ ci xj (max)

∑ aij xj = ai0 (i=1,…,m)

xj >0 (j= 1,…,n)

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

Рассмотрим суть симплекс-метода. Если в системе m<n и все m уравнений линейно независимы, иначе ранг системы равен m. Тогда система имеет бесконечное множество решений. Систему можно разрешить относительно m переменных, которым в матрице системы соответствуют линейно независимые векторы-столбцы. Обозначив эти переменные через x1 ,…,xmm +1 ,…,xn

xi = bi0 -∑ bij xm+1 (i=1,..,m)

i в целевую функцию, получаем:


f=b00 - ∑ b0 j xm + j

Значения базисных переменных xi и целевой функции f полностью определяются значениями свободных переменных xm + j .

Положим, что все bi 0>0. Тогда план x0 =(b10 ;…;bm 0 ;0…;0), полученный при нулевых значениях свободных переменных xm + j , будет невырожденным опорным, а отвечающее ему значение функции f равно, как видно b00.

Опорный план x0 соответствует базису Б0 ={x1 ;…;xm0 1 , удаляя из Б0 одну переменную и вводявместо нее другую из группы свободных. При этом в базисе Б1 опорному плану x1 соответствует значение f(x10 ). Действуя таким образом, переходят к близкому к оптимальному плану. Ввиду того что опорных планов не более С ,через конечное число шагов либо приходят к оптимальному плану, либо устанавливают, что задача неразрешима.

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


Решение задач линейного программирования вручную наиболее рационально можно выполнять именно в табличной форме. В таблицу вписывают систему ограничительных уравнений и целевую функцию в виде выражений, разрешенных относите льно начального базиса Бо1т } (табл. 2.). Левый столбец занимают базисные переменные и целевая функция, а верхнюю строку — свободные переменные. Нижнюю строку, в которую вписаны коэффициенты целевой функции f, называют f- строкой или строкой целевой функции.. За столбцом базисных переменных следует столбец свободных членов. Иногда f-строку помещают сразу же за заглавной строкой, а столбец свободных членов в конце; таблицы. Таблицы описанного вида называются симплексными.

базисные переменные 1

-xm +1 … -xm + s … -xn

x1 =

xk =

xm =

b10

bk0

bm0

b11 1s … b1,n-m

……………………………………

bk1 … bks … bk,n-m

……………………………………

bm1 … bms … bm,n-m

f= b00 b01 …b0 s …b0,n-m

Используются и другие формы симплексных таблиц, но принятая нами форма является наиболее компактной и наглядной. В ней содержится вся необходимая информация о ходе решения задачи. Если, как предполагалось выше, все bi 0 >0, то при нулевых значениях верхних (свободных) переменных столбец свободных членов дает значения базисных переменных опорного плана xо = (b10m 0 ;0; ... 0) и соответствующее значение b00 целевой функции: f(х000 .

kj k-й строки на соответствующие переменные, стоящие в заглавной строке (-xm + i ), полученные произведения сложить и сумму приравнять xk Тогда

bko *1 + bk1 (—xm+l )+ … +bks {—xm+s )+ ... + bk ,n-mn ) =xk i = bi0 -∑ bij xm+1.


Рассмотрим последовательность решения задач линейного программирования симплекс-методом и изложим ее применительно к задаче максимизации.

1. По условию задачи составляется ее математическая модель.

2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.

3. Каноническая модель задачи записывается в форме симплекс-таблицы так, чтобы все свободные члены были неотрицательными. Если начальный опорный план выделен, то переходят к пункту 5.

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

5. Найденный начальный опорный план исследуется на оптимальность:

а) если в f-строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нулевых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;

б) если в f-строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то f→ ;

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

Важно заметить, что поскольку minf= — max( —f), задачу минимизации f можно формально заменить задачей максимизации функции (—f). Но можно этого и не делать. Признаком оптимальности опорного плана задачи минимизации является отсутствие положительных элементов в f-строке симплекс-таблицы, содержащей опорный план. В остальном вычислительная процедура не меняется.

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

1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагая, что ограничения задачи совместны);

3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р -строка;

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

4. 1 Признак оптимальности опорного плана

Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2. b0 j > (i=1, ..., nm). В опорном плане х0 , содержащемся в этой таблице, значения всех свободных переменных xm + j равны нулю и f(х000 . Если же увеличивать какую-либо из свободных переменных xm + j, то, как видно из равенства (2. 5), в силу неотрицательности b0 jо функция f(х) достигает наибольшей величины, а значит, х0 действительно является оптимальным опорным планом.

4. 2 Возможность переход от одного опорного плана к другому

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

Докажем этот признак. Установим правила выбора переменных для такого преобразования начального базиса Бо с опорным планом х0 в новый базис Б1 с опорным планом х1 при котором; значение функции f увеличивается, т. е. f(xi )>f(x0 ). Тогда по правилу пересчета элементов из симплекс-таблицы преобразуем к новому базису, что позволит найти компоненты нового опорного плана.

Допустим, что в табл. 2. 1, например, b0 s<0, а среди элементов bis s-го столбца есть хотя бы один положительный. Полагая в равенстве (2. 5) все свободные переменные хm + j кроме xm + s , равными нулю, получаем f = boo — bos xm + s . Из этого равенства видно, что при увеличении xm + s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых xm + s принимает положительные значения, а все остальные компоненты xm + j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Бо1m + sоm + s

m + s ;

2) какое значение должна принимать новая базисная переменная xm + s в новом опорном плане.

Для решения поставленных вопросов допустим, что в равенствах (2. 4) все xm + j , кроме xm + s , равны нулю. Тогда

xi = bio -bis xm + s

m + s значения тех базисных переменных хiis <0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты bis можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых 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 <bdo /bds

……………… ………………

bk0 - bks xm +s >0 илиxm+s < bko /bks

……………… ………………

bp0ps xm+s >0 xm+s < bpo /bps

т. е. приxm+s<min {bdo /bds ; ...; bk0 /bks ; ...; bp0 /bpS }.

io /bis соответствует i = k, т. е.

min { bio /bisk0 /bks .


Тогда можно сказать, что пока xm + s не превышает величины bk 0 /bks , т. е. xm + s <bko /bks , все базисные переменные xi остаются неотрицательными. Если же xm + s положить равной bk 0 /bks >0, то переменная хkk = bk 0 — bks bko /bksо = {х1 ; ...; xk ; ...; хmm + s из группы свободных переходит в базисные, а переменная хkm + s1 в новом базисе Б1 ={х1 ; ...; xm + s ; ...; xm1 некоторые базисные переменные могут принять нулевые значения в двух случаях:

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

io /bis будет соответствовать двум или нескольким номерам i. В нашем же случае она соответствует только i = k.

Переменная, подлежащая включению в базис, определяется отрицательным элементом f-строки. Из равенства f =boo – bos xm + s ясно, что при b0 s <0 и фиксированном xm + s>0, значение f(х) зависит от абсолютной величины коэффициента b0 s : чем больше b0 s , тем большее значение получит f(х) в новом базисе. Но из этого равенства видно также, что значение целевой функции в новом базисе зависит и от величины, принимаемой новой базисной переменной xm + s . Будем выбирать переменную, вводимую в базис, ориентируясь лишь на отрицательные элементы f-строки. Поэтому, когда в f-строке несколько отрицательных элементов, в базис будем вводить переменную xm + j ,соответствующую отрицательному элементу с наибольшей абсолютной величиной. Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу f-строки, мы обеспечиваем возрастание функции f.

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

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

Отметим, что нам уже известно значение новой базисной переменной xm + s в новом опорном плане: оно равно bko /bks . Что же касается численных значений остальных базисных переменных в новом опорном плане и соответствующего значения f(х), то их можно найти лишь после того, как измененная система базисных переменных х1m + s ; ...,хm будет выражена через измененную систему свободных переменных xm +1 ,…,xk ,…, хn . Для этого установим; правила, по которым осуществляется преобразование условий задачи от одного базиса к другому.

ks = 0 при xm + s в этом уравнении называют разрешающим элементом. В равенстве (2. 7) новая базисная переменная xm + s выражена через свободные переменные, среди которых находится теперь и бывшая базисная переменная хk . Таким образом, переменные xm + sk

Аналогично выразим через новый набор свободных переменных и остальные базисные переменные. С этой целью значение xm + s из подставим в остальные равенств (обозначим fчерез x0 ,тогда равенство будет входить в систему при i= 0)

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

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

Докажем это утверждение. Пусть в табл. 2, например, b0 s <0, и все элементы s-го столбца неположительны, т. е. bis<0 (i=1, ..., m). Тогда, положив в уравнениях (2. 4) и (2. 5) все свободные переменные, кроме xm + s , равными нулю, получим

xi = bio - bis xm+s (i=1, ..., m)

f=boo - b0 s xm + s .

m + s можно произвольно увеличивать, не опасаясь нарушить условие неотрицательности базисных переменных xi ибо bi 0 >0, ( - bis )>0, а значит, и xi >0 при любых xm + s>0. В то же время, как видно, где (- b0 s>0, значение f(х) будет монотонно возрастать, и если

xm +. s→ , то и f→ .

4. 4 Признак бесконечности множества оптимальных планов

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

Докажем это утверждение. Допустим, что содержащийся в табл. 2 опорный план является оптимальным. Обозначим его через х1os f-строки равен нулю, а все остальные элементы этой строки положительны. Тогда, подвергнув табл. 2 симплексному преобразованию с s-м разрешающим столбцом, мы придем к другой таблице с новым опорным планом, который также будет оптимальным, поскольку элементы f-строки не изменились (нулевой элемент bos f-строки расположен в разрешающем столбце). Обозначим этот новый опорный оптимальный план через х2 *. В соответствии с основной теоремой линейного программирования утверждаем, что любой план х*, являющийся выпуклой линейной комбинацией планов х1 * и х2 *, тоже будет оптимальным.

Если в f-строке будет t(t< n - m) нулевых элементов, то описанным способом можно получить, кроме х1 *, еще t оптимальных опорных планов х2 *; …;хt +1 *, и тогда все бесконечное множество оптимальных планов запишем так:

λ1 x1λt +1 xt +1λl>0 (l=1,…,t+1) и λ1 +…+λt +1 =1

Все множество оптимальных планов можно записать в виде

х*=λх1 * + (1- λ) х2 *

Рассматривая преобразование одного базиса в другой , мы предполагали, что среди симплексных отношений имеется только одно наименьшее, и поэтому вопрос о выборе переменной, исключаемой из базиса, решался однозначно. Но если допустить, что в разрешающем столбце minbi 0 /bis достигается для нескольких индексов, например для i = l и i = t, т. е.

blo btsto bls

и разрешающей выбрана l-я строка. Тогда в новом опорном плане базисная переменная xt в соответствии с формулой (2. 8) будет равна

b'toto bls — blo bts ): bis

Отсюда получаем xt = b't 0 = 0. Таким образом, новый опорный план будет вырожденным. Задача линейного программирования, имеющая хотя бы один вырожденный опорный план, называется вырожденной.

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

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


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


1 Ашманов С. А., Линейное программирование. М.: Наука 1981.

4. Кузнецов А. В., Холод Н. И., Новикова Т. И. сборник задач по математическому программированию. Мн.: Высшая школа 1994