9. Связь угловых точек с опорными решениями.
Теорема. Любое опорное решение является угловой точкой области допустимых решений.
Теорема. Любая угловая точка области допустимых решений является опорным решением.
Если ЗЛП имеет оптимальное решение, то целевая ф-ия принимает его в одной из угловых точек многоугольника решений. Пусть Х* явл-ся опт-решением. Тогда значение целевой ф-ии в этой точке F(X*)>=F(Xi), i=1,n. Если Х* явл-ся одной из угловых точек, то теорема доказана.
10. Теорема о симплексных преобразованиях. В результате симплексных преобразований свободные члены сохраняют свою неотрицательность.
Док-во:
/ bk’= (aij*bk - akj*bi)/aij=bk- akj* (bi/aij)=aki(>0)(bk/akj – bi/aij)>0, чтд.
11. Нахождение исходного опорного решения. При приведении системы к единичному базису, некот свободные члены могут оказаться отрицательными. Тогда выполн. след. действия:
1. Фиксируют ур-ие с наиб. по модулю отриц. свободным членом.
2. Вычитают фиксированное уравнение из всех уравнений с отриц. свободными членами. При этом, свободные члены становятся положительными.
3. Фиксированное уравнение умножаем на (-1).
4. Все ур-ия с положит свободными членами оставляем без изменений. В итоге получается система с неотриц. Свободными членами.
При этом возможно несколько случаев.
Если все коэф-ты в фиксир. Ур-ии отриц-ные, система не имеет решений;
Если разрешающий элемент попадает в фиксированное ур-ие, система разрешима за 1 шаг;
Если разреш-ий элемент не попал в фиксир-ое ур-ие, то с помощью преобразований приводим систему к случаю 1 иил 2.
12. Преобразование целевой ф-ии. Для преобразования целевой ф-ии проводится т.н. анализ чувствительности. Анализом чувствительности называется изучение влияния изменения параметров полученной модели на оптимальное решение. При этом возникает ряд вопросов: 1. Можно ли увеличить или уменьшить запас сырья для улучшения полученного значения опт-функции? 2. Увеличение какого ресурса наиб. выгодно? 3. В каких пределах могут изменяться коэффициенты целевой ф-ии при неизменности опт-решения?
Ограничение называется активным, если в точке опт-решения выполняется как равенство, и неактивным, если выполняется как строгое неравенство.
Ресурс называется дефицитным, если соответствующее ему ограничение явл-ся активным.
Чтобы графически определить максимальное увеличение запаса дефицитного ресурса, вызывающее улучшение оптимального решения, необходимо передвигать соответствующую прямую в направлении улучшения ЦФ до тех пор, пока это ограничение не станет избыточным.
Чтобы численно определить максимальную величину запаса дефицитного
ресурса, вызывающую улучшение оптимального решения, необходимо: 1) определить координаты точки, в которой соответствующее ограничение становится избыточным;
2) подставить координаты в левую часть соответствующего ограничения. Чтобы определить максимальное уменьшение запаса недефицитного ресурса, не меняющее оптимальное решение, необходимо передвигать соответствующую прямую до пересечения с оптимальной точкой.
Мера чувствительности стоимости единицы ресурса – yi – равна отношению изменения значения целевой ф-ии к изменению объема ресурса. На основании полученных данных можно определить, насколько изменится стоимость (т.к. при изменении объемов используемых ресурсов изменится цена). Также можно определить пределы изменения коэффициентов целевой ф-ии.