Алгоритм симплекс-метода


I. После введения добавочных переменных, система уравнений записывается в виде, который называется расширенной системой (11). Предполагается, что все добавочные переменные имеют тот же знак, что и свободные члены.

II Исходную расширенную систему заносим в первую симплекс таблицу. Последняя строка, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком. В левом столбце таблицы записываем базисные переменные (на первом шаге за базисные переменные берутся дополнительные переменные), в первой строке - все переменные, во втором столбце - свободные члены расширенной системы . Последний столбец подготовлен для оценочных отношений, необходимый при расчете. В рабочую часть таблицы, начиная с третьего столбца и второй строки, занесены коэффициенты, при переменных ау расширенной системы. Далее таблица преобразуется по определенным правилам.

III. Проверяем выполнение критерия оптимальности (при решении задачи на максимум критерий оптимальности состоит в отсутствии отрицательных коэффициентов в оценочной строке). Если критерий оптимальности выполнен, то следовательно, максимум достигнут и оптимальное значение равно (в левом нижнем углу таблицы). Базисные переменные принимают значения остальные переменные равны . Если критерий оптимальности не выполнен, переходим к следующему шагу.

IV. По оценочной строке выбираем переменную, вводимую в базис. Находим наибольший по модулю отрицательный коэффициент в оценочной строке. Соответствующая этомустолбцу переменная будет вводимой в базис, а сам столбец называется разрешающим.

V. Находим переменную, выводимую из базиса. Для этого составляем оценочные отношения (они заносятся в столбец для оценочных отношений) по следующим правилам:

1) , если и имеют разные знаки;

2) , если и ;

3) ли ;

4) 0, если и ;

5) , если и имеют одинаковые знаки.

Определяем . Если конечного минимума нет, то задача не имеет конечного оптимума Если минимум конечен, то выбираем строку q, на которой он достигается (если их несколько, то любую), и называем ее разрешающей строкой. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент .

VI. Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана):

1) В левом столбце записываем новый базис: вместо основной переменной - переменную ,

2) В столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1 - на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 - во всех других позициях столбцов базисных переменных.

3) Новую строку получаем из старой делением на разрешающий элемент .

4) Все остальные элементы вычисляем по правилу прямоугольника:

(12)

Далее переходим к шагу III.

Пример.Решить задачу:

Приведем систему ограничений к каноническому виду. Получим расширенную систему:

Целевую функцию представим в виде

Базисными переменными будут являться дополнительные переменные .

Заполняем первую симплекс-таблицу:

 

Базис Свободный Переменные Оценочные
  член             отношения
   
18/3
-2 -3  

 

Проверяем критерий оптимальности задачи. В последней оценочной строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю - (-3). Следовательно, . Переменная является выводимой из базиса а соответствующий ей столбец - разрешающим.

Находим оценочные отношения и выбираем из них минимальное (5). Следовательно, , переменная является вводимой в базис, а соответствующая ей строка - разрешающей.

Переходим к новой симплекс-таблице:

а) в новом базисе основные переменные ;

б) расставляем 0 и 1; например, на пересечении столбца и строки, соответствующих переменной ставим 1, а остальные элементы столбца равны 0 и т.д. Третья строка получается делением на разрешающий элемент . Остальные клетки таблицы заполняем по формулам (12). Например:

Получаем вторую симплекс-таблицу:

 

Базис Свободный Переменные Оценочные
  член             отношения
   
-3
-1 11/2
-2  

 

Критерий оптимальности вновь не выполнен. Теперь разрешающий первый столбец и - вводимая переменная. Считаем оценочные отношения и находим разрешающую строку - первая и выводимую из базиса переменную - .Разрешающий элемент .

Переходим к новой симплекс-таблице:

 

Базис Свободный Переменные Оценочные
  член             отношения
   
-3
-2 5/5
5/1
-3 12/9
-3  

 

и на этот раз критерий оптимальности не выполнен.

Выводимая переменная ; вводимая переменная- . Переходим к новой таблице.

 

Базис Свободный Переменные Оценочные
  член             отношения
   
-1/5 3/5  
-2/5 1/5  
2/5 -1/5
3/5 -9/5  
4/5 3/5  

 

Критерий оптимальности выполнен. Следовательно, Оптимальное решение

 



Дата добавления: 2017-04-05; просмотров: 1392;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.011 сек.