Курсовая работа: Применение симплекс-метода

Для решения задач линейного программирования существует множество методов. Рассмотрим один из них.

Улучшенный (модифицированный) симплекс-метод

Для начала расскажем, что такое симплекс-метод. Слово SIMPLEX в обычном смысле означает простой, несоставной, в противоположность слову COMPLEX.

Данный метод получил несколько различных форм (модификаций) и был разработан в 1947 году Г. Данцигом.

Сущность симплекс-метода заключается в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.

В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях и несколько оптимальных решений, но все они обеспечат экстремум целевой функции. Таким образом, если найти какой-либо базисный план, а затем улучшить его, то получится оптимальное решение. На этом принципе и построен симплекс-метод.

Одним из модификаций симплекс-метода является улучшенный симплекс-метод.

В литературе этот метод встречается также под названием метода обратной матрицы или модифицированного симплекс-метода.

При решении задач линейного программирования, в которых n (количество переменных) существенно больше m (количество ограничений), улучшенный симплекс-метод требует по сравнению с другими значительно меньшего количества вычислительных операций и объема памяти ЭВМ.

В улучшенном симплекс-методе реализуется та же основная идея, что и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается не вся матрица A^-1 , обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису A_x .

Рассмотрим поэтапно шаги решения задачи линейного программирования улучшенным симплекс-методом:

1.В начале первого цикла нам известны обратная матрица (единичная матрица), базисное решение x_b = b.

2.Образуем для каждой небазисной переменной характеристическую разность D_j , используя уравнение:

D_j = c_j — = c_j — pP_j ,

Где p - двойственные переменные, которые можно найти следующим образом:

p = c_{x *} ,

Где c_x - вектор коэффициентов целевой функции при базисных переменных.

3.Предполагая, что используется стандартное правило выбора вводимого столбца, находим:

.

4.Если D_s ³ 0 - процедура останавливается. Текущее базисное решение является оптимальным.

5.Если D_s £ 0, вычисляем преобразованный столбец:

= P_s

6.Пусть

= (, , ..., ) .

Если все £ 0 - процедура останавливается: оптимум неограничен.

7.В противном случае находим выводимую из базиса переменную:

= q .

8.Строим увеличенную матрицу:

-1;\s\do(x:;:;: