- •1 Теорема:
- •6) Канонический вид злп; разрешенный и допустимый канонический вид. Использование канонической формы в симплексном методе. Критерий допустимости и критерий оптимальности.
- •7) Метод искусственного базиса для нахождения вершины. Искусственные переменные и недопустимость множества решений злп.
- •9) Двойственные задачи. Двойственность в линейном программировании. Правила построения двойственных задач
- •Правила построения пары двойственных задач
- •Исследование моделей задач лп на чувствительность.
- •12. Транспортная задача. Общая постановка транспортной задачи. Свойства множества решений. Методы нахождения первой вершины.
- •Метод потенциалов.
- •15. Вырожденность в транспортных задачах и приемы борьбы с зацикливанием. Задача о назначениях как частный случай вырожденной транспортной задачи
- •Задача о назначениях
- •16) Элементы целочисленного программирования. Метод Гомори построения отсечений и двойственный симплексный метод.
Исследование моделей задач лп на чувствительность.
Анализ модели на чувствительность связан с исследованием возможных изменений полученного оптимального решения в результате изменений исходной модели.
Пусть в исходной модели изменяются ресурсы
Возникает два вопроса.
1. Какие изменения ресурсов не влияют на оптимальный план х* ?
2. Запасы каких ресурсов необходимо увеличивать в первую очередь для получения максимальной дополнительной прибыли ?
Ответ на первый вопрос. Если оценка i-го ресурса
то этот ресурс не является существенным и вполне возможно его уменьшение на величину
Причем это уменьшение не повлияет на оптимальность плана х*.
Ответ на второй вопрос. Чем больше оценка i-го ресурса
тем существеннее вклад i-го ресурса в функцию максимального дохода L* и тем выше приоритет соответствующих видов ресурсов при решении вопроса распределении дополнительных затрат по видан ресурсов.
Пусть изменяются коэффициенты в ограничениях
Эти изменения связаны с изменением потребления ресурсов в производственно-технологических процессах. Аналогично тому, как это делается при установлении приоритетности ресурсов, двойственные оценки используются и при решении вопроса о том, совершенствование какого участка производства является первоочередным. Чтобы сделать производство j-й продукции более прибыльным, необходимо снизить соответствующую ему суммарную ценность ресурсов
При этом главное внимание уделяется уменьшению величины соответствующей наибольшей двойственной оценке Технический аспект, связанный с уменьшением величины определяется внутренними характеристиками системы.
Двойственность для задач ЛП позволяет исследовать некоторые дифференциальные свойства функции оптимума optL, где L -- произвольная задача ЛП, .
Пусть
|
(8.1) |
Теорема о маргинальных значениях для L - это теорема о формульном представлении производной функции оптимума по произвольному направлению l из пространства вектора y. Примем в качестве l вектор . Частный случай этой ситуации реализуется соотношением
|
(8.2) |
в котором роль направления l играет вектор в пространстве вектора b (как информационного параметра задачи L), т.е. . Если оптимальный вектор исходной задачи (8.1) единственный, то имеет место аналог соотношения (8.2) в форме
|
(8.3) |
где . В общем случае получение формулы для выводит за рамки линейного анализа линейной задачи L.
Теорема 8.1 Пусть выполнены для задачи L условия: 2. Оптимальные множества и не пусты и ограничены. Если - произвольное направление в пространстве вектора , то
|
(8.4) |
Следовательно, если L и разрешимы в единственных точках и , то
|
С симплекс-множителями мы сталкиваемся при решении транспортной задачи. Иногда их также называют потенциалами, а метод решения при их помощи – методом потенциалов. Они являются двойственными переменными, соответствующими ограничениям на спрос и предложение пунктов назначения и отправления соответсвенно. Симплекс множители ui и vj нужны для того, чтобы найти свободную ячейку (i, j), которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс методе).