§9. Критерии оптимальности симплекс - метода.
Задача на max: если в выражении целевой функции Z через свободные переменные, отсутствуют отрицательные коэффициенты при свободных переменных, то решение оптимальное.
Задача на min: если в выражении функции Z через свободные переменные отсутствуют положительные коэффициенты при них, то решение оптимальное.
8. Симплекс-метод. Переход от системы ограничений к симплекс-таблице №1
Симплекс - метод представляет собой схему перехода от одного базисного решения к другому и т.д., пока не будет найдено оптимальное решение или выяснится, что система ограничений противоречива.
Пусть требуется найти максимум целевой функции:
Если система ограничений задана в стандартной форме, то следует перейти к канонической, вводя вспомогательные положительные переменные.
Разрешим систему ограничений относительно вспомогательных переменных.
Перепишем целевую функцию в виде:
Составим симплекс таблицу №1:
б\св
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Z
...
...
0
а) Просматриваем элементы строки Z (кроме элементов свободных членов). Если в строке Z нет отрицательных элементов, то функцию увеличивать нельзя и Z принимает максимальное значение при равенстве нулю всех свободных переменных по критерию оптимальности для максимума, т.е.
б) Если в Z строке есть отрицательные элементы, то функцию Z можно увеличивать. Для этого по строке Z выбирают наименьший отрицательный элемент (наибольший по модулю). Это означает, что столбец, в котором стоит данный элемент - разрешающий столбец. Для определения разрешающей строки составляют отношения свободных членов к положительным элементам разрешающего столбца и выбирают минимальное:
(не
делят на ноль)
Элемент, стоящий на пересечении разрешающей строки и столбца, называется разрешающим элементом. Итак:
Если i-я строка - разрешающая,
j-й столбец - разрешающий, то
- разрешающий элемент.
9. Алгоритм перехода от симплекс-таблицы №1 к симплекс-таблице №2
Алгоритм перехода к симплекс - таблице 2:
Меняем местами переменные и .
Разрешающий элемент берем обратный самому себе
.Остальные элементы разрешающей строки делим на разрешающий элемент.
Все элементы разрешающего столбца делим на разрешающий элемент, взятый с противоположным знаком.
Все остальные элементы таблицы просчитываем по правилу прямоугольника:
Получено новое допустимое значение Z при свободных переменных равных нулю и соответствующих значениях базисных переменных.
Если в Z-й строке все элементы
,
то функция достигла максимума
(оптимальное решение) - задача решена.
Если в строке Z есть отрицательные элементы, то переходим к симплекс-таблице 3 и т. д., пока все элементы по строке Z будут или не выяснится, что условия задачи противоречивы.
Замечания:
Аналогично решается задача на минимум, но теперь следует избавляться от положительных элементов в Z-й строке. Если в этой строке нет положительных элементов, то задача решена.
Если в разрешающем столбце нет положительных элементов, то нельзя составить отношения и задача не разрешима.
Если первоначальное базисное решение не является допустимым
,
то применяется метод искусственного
базиса.
10. Двойственность в задачах линейного программирования. Свойства двойственности
Каждой задаче линейного программирования соответствует двойственная или сопряженная задача.
-
Задача 1 (исходная)
Задача 2 (двойственная)
Составить такой план выпуска продукции Х
,
при котором прибыль от реализации
будет максимальной при условии, что
потребление ресурсов по каждому виду
продукции не будет превосходить
имеющиеся запасы.
Найти такой набор ценовых ресурсов У
,
при котором общие затраты на ресурсы
будут минимальными при условии, что
затраты на ресурсы при производстве
продукции каждого вида, будут не менее
прибыли от реализации этой продукции.
Свойства двойственных задач:
В первой задаче ищется
целевой функции, а в другой
.Коэффициенты при переменных целевой функции одной задачи являются свободными членами системы ограничений другой задачи.
Каждая из задач задана в стандартной форме.
Матрицы коэффициентов при переменных в системах ограничений являются транспонированными друг другу.
Число неравенств в первой задаче, совпадает с числом переменных в другой задаче.
Условия неотрицательных переменных присутствуют в обеих задачах.
11. Алгоритм составления двойственной задачи
Алгоритм составления двойственной задачи:
Привести все неравенства системы ограничений исходной задачи к одному смыслу. Для этого неравенства, в которых данные требования не выполняются, умножают на (-1).
Составляют расширенную матрицу исходной задачи. В нее входят:
коэффициенты при переменных системы ограничений;
столбец свободных членов;
строка коэффициентов при переменных целевой функции.
Транспонируем полученную матрицу.
Формулируем двойственную задачу на основании полученной матрицы и условии неотрицательных переменных.
Теорема.
Если
одна из двойственных задач имеет
оптимальный план, то и другая также
имеет оптимальный план, причем оптимальные
значения целевых функций равны, т.е.
Если целевая функция одной из задач неограниченна, то условия другой задачи противоречивы, следовательно, оптимального плана нет.
Пример: Исходная задача:
Составить ей двойственную и решить обе задачи.
Двойственная задача: