Шпаргалка по "Математике"

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9. Переход от  общей задачи линейного программирования  к канонической форме записи

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

 

1. Если в исходной задаче  некоторое ограничение (например, первое) было неравенством, то оно  преобразуется в равенство, введением  в левую часть некоторой неотрицательной  переменной, при чем в неравенства  «≤» вводится дополнительная  неотрицательная переменная со  знаком «+»; в случаи неравенства  «≥» - со знаком «-»

(2.10)

Вводим переменную

.

Тогда неравенство (2.10) запишется  в виде:

(2.11)

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

 

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

, l - свободный индекс

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

4. Наконец, если  исходная задача была задачей  на минимум, то введением новой  целевой функции F₁ = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁.  

 

 

 

 

 

 
 
 

 

 

 

 

 

 

 

10. Графический  способ решения ЗЛП с двумя  переменными.

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

Задача  с 2мя переменными.

Такая задача записывается в след.виде:

                         (2.20)

                                 (2.21)

                                                   (2.22)

Областью доп.решения 2.21, 2.22 могут быть либо выпуклый многоугольник, либо вып-ый многоуг. Неогр.области, либо пустая область, либо единственная точка.

Ур-ие 2.20 определяется на плоскости Х₁0Х₂ семейством || прямых, кажд.из которых отвечает определённым значениям параметра f. Вектор, перпендик. К этим прямым (при условии, что масштабы по осям координат одинаковы), указ. Направление найскорейшго возрастания параметра f функции 2.20, а противоположный вектор -направление найскорейшего убывания f.

Если в одной и той  же системе координат построить  область доп.решения системы 2.21, 2.22 и семейство прямых 2.20, то задача определения точки макс. Функции f сведётся к нахождению дополнительной области, через кот. проходит прямая f=const и соответственно наибольшему значению параметра f.

Для практического решения 2.22 необходимо построить:

1. Область дополнительных решений
3. Перпендикулярно ему одну из прямых семейства f=const. (напр. f=0) в направлении вектора С.

Искомая точка А найдётся || ым перемещением вспомогательной прямой f=0 в направлении вект. С . В противоположной вершине Вв доп. Области функция f достигает минимума. Координаты точки А/В можно определить по чертежу или решив совместное ур-ие прямых, пересекающихся в этих точках.

 

 

 

 

 

 

 

 

 

 

 

 

 

11. Основная идея  симпликс метода (СМ).

Графический способ применим к узкому классу ЗЛП, так как им эффективно решаются задачи, содержащие не более 2ух переменных.

Универсальным методом является СМ или метод последующего улучшения плана.

Пусть задана ЗЛП в каноническом виде:

  (max)        (3.1)

     i=1,m      (3.2)

X_j>=0, j=1,n

Если 3.3 разреш., то её оптимальный план совпадает по крайней мере с одним из опорных решений уравнений системы 3.2. Этот опорный план будет отыск-ся СМ в виде упорядоченного перебора опорных планов.

Т.е. при переходе от одного опорного плана к др. соотв-му значению целевой функции 3.1 возрастают (не убывают).

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

Решение зад. 3.1-3.3 состоит  из 2ух этапов:

1. Находят какой-либо начальный опорный план
2. По специальным правилам переходят от начального плана к др. более близкому оптимальному опорному плану . Затем к другому.
3. С геометрической точки зрения перебор опорных планов идентичен переходу по рёбрам из одной вершины многогранников в др., в кот.целевая функция достигает max значения.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12. Нахождение  начального опорного плана.

Алгоритм нахождения начального плана зад.3.1-3.3:

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

Разрешающая строка определяется по наименьшему из отношений свободных  членов соответствующим им положительным  элементам разрешающ.стб. Такие отношения называются симпликсными. В ходе жордановых исключений, столюцы, с перебр.наверх таблицы 0ыми знач., вычёркиваются.   Строка, состоящая из одних одних нулей, также вычёркивается. Если в процессе исключения остаются 0ые строки, то система уравнений решения не имеет.Если система уравнений совместна, то через некоторое число шагов все 0 в левом стб. Будут замещены Х-ами и тем самым получен некоторый базис и отв-ий ему опорный план.         Табл.3.2

	1	-xr+1	…..	xn
X1=	b10	b11	…..	b1,n-r
…..	…..	…..	…..	…..
Xr=	br0	br1	…..	br,n-r
f=	b00	b01	…..	b0,n-r

 
Чтобы выписать из табл.3.2 эл-ты опорного плана, необходимо положить равными 0 свободные  переменные, тогда базисные переменные будут равны соответствующим  свободным членам. Х1=b10, …, xr=br0, …, Xr+1=0, …Xn=0;     .   В п.1 алгоритма предполагалось, сто все элементы столбца свободных членов неотриц.(это треб. Не обяз, но если оно вып-но, то все послед-иежорд.исключения выполняются только с положительными разрешающими элементами, что удобно при вычислениях). В случае, когда в стб.свободных членов имеются отриц.числа, разреш.элемент выбирают следующим образом: 1.Просматривают строку, отвечающую какому-либо отрицательному члену (t-строка)и выбирают в ней какой-либо отрицательный элемент, а соотв.стб. принимают за разрешающий. (при условии, что ограничение зад. Совместно). 2. Составляем отношения элементов стб.своб.членов и соотв.элементом разрешающего столбца, и имеющ. Одинак.знаки.(симпликсн.отнош.) 3. Из симпликсных отношений выбирают наименьшее. Оно определяет разрешающую строку. 4. На пересечении разреш.стб. и стр.находятразреш.элемент, с кот. и делают шаг жорд.искл.

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

 

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

Алгоритм исследования нахождения опорного плана  на оптимальность.

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

Если 

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

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

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

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

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

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

Замечание! Т.к.   задачи минимизации можно формально заменить на задачиmax(-f) (можно этого и не делать)

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

 

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

Допустим, что отношения   достигается для нескольких индексов. Например для i=e, i=t=*  и разрешающей выбрана l* строка, тогда в новом опорном плане базис переменной i* в соответствии с правилом прямоугольника =   отсюда в соответствии (*) получаем

Таким образом новый опорный план будет вырожденным. ЗЛП имеющие хотя бы один вырожденный план называется вырожденной.

Все выводы сделанные применительно к невырожденным ЗЛП остаются верными.

14. Понятие о проблеме  вырождения. Зацикливание. Алгоритм симплекс-метода.

Если при решение вырожденной задачи на очередном шаге симплексного преобразования, разрешающая строка, в которой свободный член=0, то 0 будет равно и новая базисная компонента опорного плана. А значения остальных базисных компонентов остаются прежними. После нескольких шагов сопровождающихся пост.значениемf переходят к опорному плану с бОльшим, чем прежде значением f и решение задачи должно закончиться. Не исключается случай когда после нескольких повторений операций (итераций) получают тот же базис

 Таким образом, обнаруживается  зацикливание в схеме расчетов.

Правило позволяющие предотвратить зацикливание

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

15. Метод искусственного базиса.

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

Существует другой метод  начального плана.

На ряду с исходной задачей , , рассмотрим расширенную задачу состоящую на основе исходной след.образом

Предположим, что в 3.2… и введем в каждое из уравненйи по одной неотрицател.переменной , кот будет наз искусственными, а из их линейн.формы 3.1 вычтем сумму искусств переменных умноженную на сколько угодно большое число М-задач

 

(3.4)

(3.5)