Математические методы исследования операций в экономике (стр. 15 из 37)
и исходный сопряженный базис, образуемый векторами аn+1,аn+2,…., аn+m. При этом начальный псевдоплан равен
Таким образом, при решении задачи вида (1.66)-(1.68) двойственный симплекс-метод имеет несомненные преимущества по сравнению с прямым.
Другое важное направление использования двойственного симплекс-метода связано с поиском оптимальных планов в тех задачах, условия которых претерпели некоторые изменения после того, как они уже были решены с помощью стандартной симплекс-процедуры. Типичными примерами таких изменений являются:
- изменение компонент вектора ограничений b, что, допустим, может быть интерпретировано как корректировка объемов доступных ресурсов в процессе управления экономическим объектом;
- добавление новых ограничений к системе условий задачи, что достаточно часто случается при совершенствовании используемой экономико-математической модели.
В первом случае, т. е. при изменении вектора b, достоинства двойственного симплекс-метода очевидны, так как ранее найденный оптимальный базис можно использовать в качестве исходного сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл. 4 при рассмотрении методов решения целочисленных задач.
В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что существует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознакомиться в [1]. Отметим лишь, что она обладает теми же принципиальными преимуществами, что и модифицированный симплекс-метод.
1.7.4. Пример решения ЗЛП двойственным симплекс-методом. Рассмотрим на конкретном, примере процесс решения КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений b в результате которых
Содержание исходной симплекс-таблицы T(1)(за исключением столбца b(β(1))) будет идентично содержанию таблицы, получающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для вычисления значений b(β(1)) в данном случае можно воспользоваться обратной матрицей, полученной на последней итерации в п. 1.5.2: 
В результате имеем:
Как видно из таблицы Т(1), в столбце b(β(1)) содержатся отрицательные элементы b1(β(1)) = - 1/3<0), то есть базис β(1) ={ 
5, 1, 3} не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b(β(1)) является единственным, поэтому номер столбца, выводимого из базиса, определяется однозначно — r =1 и N1(β(1))=5. Далее рассматриваем строку a1(β(1)) = (0, -1/6, 0, -1/6, 1). В ней имеются отрицательные элементы. Вычисляем λ2 =42:(-(-1/6))=252, λ4 =38:(-(-1/6))=228. λ2> λ4, следовательно, номер столбца, вводимого в базис — l =4. Осуществляем преобразование иполучаем симплекс-таблицу T(2). 
Поскольку b(β(2))>0, то достигнутый базис N(β(2))={4,1,3} является оптимальным. Из Т(2) можно выписать оптимальный план х* =(6, 0, 32/3, 2, 0) и соответствующее ему значение целевой функцииf(x*)= 444.
- Общая задача линейного программирования (ОЗЛП).
- Каноническая задача линейного программирования(КЗЛП).
- Допустимый план.
- Оптимальный план.
- Первая геометрическая интерпретация ЗЛП.
- Базисное решение ЗЛП.
- Вторая геометрическая интерпретация ЗЛП.
- Вырожденный и невырожденный план ЗЛП.
- Симплекс-метод — метод последовательного улучшенияплана.
- Критерий оптимальности допустимого базисного плана.
- Метод минимизации невязок.
- Модифицированный симплекс-метод — вычислительнаясхема, связанная с преобразованием обратных матриц.
- Двойственная задача линейного программирования.
- Симметричность отношения двойственности.
- Теоремы двойственности.
- Экономическая интерпретациядвойственных оценок.
- Параметрическая устойчивость решения ЗЛП.
- Двойственный симплекс-метод — метод последовательного уточнения оценок.
- Сопряженный (двойственно допустимый) базис.
- Опорный план и псевдоплан.
1.1. Сформулируйте задачу линейного программирования.
1.2. Дайте определение для следующих понятий: план, допустимый план, оптимальный план,
решение задачи.
1.3. Чем отличается общая задача линейного программирования от канонической?
1.4. Всегда ли общую задачу линейного программирования можно привести к каноническому виду?
1.5. Дайте определения для следующих понятий: аффинное множество, гиперплоскость, базис.
1.6. Чем отличается выпуклый многогранник от многогранного выпуклого множества?
1.7. В чем отличие понятий «линейная оболочка» и «выпуклая оболочка»?
1.8. Любой ли конус является выпуклым множеством?
1.9. Какая точка выпуклого множества называется угловой?
1.10. В чем заключается первая геометрическая интерпретация задачи линейного программирования?
1.11. В чем заключается вторая геометрическая интерпретация задачи линейного программирования?
В чем ее отличие от первой?
1.12. Какой план называется базисным?
1.13. Как связаны базисные планы и угловые точки области определения задачи линейного
программирования?
1.14. Какой план задачи линейного программирования называется вырожденным?
1.15. Как с точки зрения второй геометрической интерпретации можно представить процесс поиска
оптимального плана в задаче линейного программирования?
1.16. Сформулируйте критерий оптимальности допустимого базисного плана, применяемый в
симплекс-методе.
1.17. Сформулируйте основные этапы стандартной итерации симплекс-метода.
1.18. Для чего применяется преобразование Жордана—Гаусса?
1.19. Какой элемент симплекс-таблицы называется ведущим?
1.20. При каких условиях делается вывод о неограниченности целевой функции в решаемой задаче?
Какая геометрическая интерпретация соответствует данному случаю?
1.21. Можно ли заранее точно определить количество итераций, которое потребуется для решения
задачи симплекс-методом? Можно ли найти верхнюю границу для данной величины?
1.22. Какая задача называется вырожденной? По каким признакам можно узнать, что текущий план
является вырожденным?
1.23. Какие проблемы возникают при решении вырожденных задач?
1.24. Какую экономическую интерпретацию имеет ситуация вырожденности?
1.25. В чем основная идея метода возмущений?
1.26. Для чего предназначен метод минимизации невязок?
1.27. Сформулируйте основные отличия модифицированного симплекс-метода по отношению к
стандартному.
1.28. Перечислите преимущества модифицированного симплекс-метода.
1.29. Будет ли отличаться количество итераций при решении одной и той же задачи при решении ее
стандартным и модифицированным симплекс-методом?
1.30. Дайте определение двойственной задачи.
1.31. Какими основными свойствами обладает пара двойственных задач?
1.32. В чем заключается экономическая интерпретация переменных двойственной задачи?
1.33. Какой смысл вкладывается в понятие «параметрическая устойчивость»?
1.34. Сформулируйте условия для допустимых изменений целевой функции задачи, при которых ее
оптимальный план остается неизменным.
1.35. Перечислите основные идеи, на которых базируется алгоритм двойственного симплекс-метода.
1.36. Дайте определение сопряженного базиса.
1.37. Что такое псевдоплан?
1.38. Сформулируйте критерий оптимальности, используемый в алгоритме двойственного симплекс-
метода.
1.39. По каким признакам можно определить, что множество допустимых планов задачи, решаемой
двойственным симплекс-методом, пусто?
1.40.В каких ситуациях могут быть реализованы преимущества двойственного симплекс-метода?
ГЛАВА 2. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
2.1.1. Постановка задачи. Как уже упоминалось во введении, предположение о возможности описать зависимости между управляемыми переменными с помощью линейных функций далеко не всегда адекватно природе моделируемого объекта. Например, в рассмотренных в главе 1 моделях цена товара считается независимой от количества произведенного продукта, однако в повседневной жизни мы постоянно сталкиваемся с тем, что она может зависеть от объема партии товара. Аналогичные замечания могут быть сделаны и по поводу технологических ограничений: расход определенных видов сырья и ресурсов происходит не линейно, а скачкообразно (в зависимости от объема производства). Попытки учесть эти факторы приводят к формулировке более общих и сложных оптимизационных задач. Изучение методов их решения составляет предмет научной области, получившей названия нелинейного программирования.