Дипломная работа: Решения задачи планирования производства симплекс методом
1). Находят решение задачи линейного программирования (1)-(3).
2). Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
3). Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
4). В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение.
Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.
Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори.
В узлах метода ветвей и границ используется симплекс-метод.
Главный недостаток алгоритма метода ветвей и границ заключается в необходимости полностью решать задачи линейного программирования, ассоциированные с каждой из вершин многогранника допустимых решений. Для задач большой размерности это требует значительных и, в известной степени, неоправданных с практической точки зрения затрат времени.
2.3 Симплекс метод
Задачи линейного программирования в канонической форме широко распространены в инженерной практике, и для их решения разработана большая группа методов, основной из которых — симплекс-метод. Рассмотрим постановку и решение задачи линейного программирования в канонической форме.
2.3.1 Описание
Задача будет рассматриваться в форме, которая называется канонической. Известно, что путем введения дополнительных ограничений и переменных можно свести к канонической форме задачу линейного программирования, представленную в любой форме, в частности в естественной форме.
2.3.2 Алгоритм симплекс-метода
2.3.2.1 Усиленная постановка задачи
Задачи линейного программирования имеет следующий вид:
с помощью конечно-сходящейся вычислительной процедуры симплекс-метода, заданной оператором
В операторе векторы 
и 
— оптимальное решение задачи и начальное приближение для симплекс-метода, которые в симплекс-методе являются базисными решениями, определяемыми ниже. Векторы 
и 
представляют собой последующее и предыдущее решения в симплекс-методе.
2.3.2.2 Алгоритм
Алгоритм симплекс-метода формулируется для задачи линейного программирования следующим образом:
Шаг 1. Формулировка задачи линейного программирования в канонической форме на основе метода искусственного базиса, так чтобы в матрице ограничений существовала единичная базисная матрица. Для этого необходимо дополнить матрицу ограничений единичными столбцами, которые должны в совокупности с исходными столбцами матрицы ограничений обеспечивать существование единичной базисной матрицы. При этом естественным образом должны быть введены соответствующие искусственные переменные, которые включаются в целевую функцию с большими положительными весовыми коэффициентами для задачи на минимум. В результате запишем исходную матрицу ограничений 
. в симплекс-таблицу(*), а коэффициенты целевой функции 
запишем в строку этой таблицы. В таблицу(*) также включим компоненты исходного базисного решения, определяемого вектором 
Таблица (*)
| #№ | Базисные столбцы | Bs | Базисное решение Xs | C1 | C2 | … | Cm
К-во Просмотров: 312
Бесплатно скачать Дипломная работа: Решения задачи планирования производства симплекс методом
|