Решения задачи планирования производства симплекс методом

Рефераты / Экономико-математическое моделирование / Решения задачи планирования производства симплекс методом

Итак, процесс нахождения решения задачи целочисленного программирования (1)-(4) методом ветвей и границ включает следующие основные этапы:

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. Формулировка задачи линейного программирования в канонической форме на основе метода искусственного базиса, так чтобы в матрице ограничений существовала единичная базисная матрица. Для этого необходимо дополнить матрицу ограничений единичными столбцами, которые должны в совокупности с исходными столбцами матрицы ограничений обеспечивать существование единичной базисной матрицы. При этом естественным образом должны быть введены соответствующие искусственные переменные, которые включаются в целевую функцию с большими положительными весовыми коэффициентами для задачи на минимум. В результате запишем исходную матрицу ограничений . в симплекс-таблицу(*), а коэффициенты целевой функции запишем в строку этой таблицы. В таблицу(*) также включим компоненты исходного базисного решения, определяемого вектором