[Список тем] [Вступление к этой теме] страницы темы: [1] [2]

Симплексные таблицы.

При решении реальных задач симплексным методом удобно использовать симплексные таблицы. Далее мы рассмотрим алгоритм их составления, не углубляясь в его подробное обоснование. Для определенности считаем, что решается задача на отыскание максимума.
I. После введения выравнивающих переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:
а₁₁ х₁+а₁₂ х₂+...+а_1n х_n + х_n+1 = b₁
а₂₁ х₁+а₂₂ х₂+...+а_2n х_n + х_n+2 = b₂
...
а_m1 х₁+а_m2 х₂+...+а_mn х_n + х_n+m = b_m
F - с₁х₁- с₂х₂-...- с_nх_n = 0.

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены; в противном случае используем так называемый М-метод, который рассмотрим позже.

II. Исходную расширенную систему заносим в первую симплексную таблицу.

• Последняя строка таблицы заполняется коэффициентами функции цели с противоположным знаком: b_i = - с_i.
• В левом столбце таблицы записываем основные переменные (базис),
• в первой строке таблицы - все переменные (отмечая при этом основные),
• во втором столбце - свободные члены расширенной системы b₁, b₂, ..., b_m.
• Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной.
• В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты a_ij при переменных из расширенной системы.

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

III. Проверяем выполнение критерия оптимальности при решении задачи на максимум - наличие в последней строке отрицательных коэффициентов b_i < 0 (с_i > 0). Если таких нет, то решение оптимально, достигнут max F = с₀ (в левом нижнем углу таблицы), основные переменные принимают значения a_i0 (второй столбец), неосновные переменные равны 0, т.е. получаем оптимальное базисное решение.

IV. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент b_i < 0 в последней строке определяет разрешающий столбец s.
Составляем оценочные ограничения каждой строки по следующим правилам:
1) , если b_i и a_is имеют разные знаки;
2) , если b_i = 0 и a_is < 0;
3) , если a_is = 0;
4) 0, если b_i = 0 и a_is > 0;
5) | b_i / a_is | если a_is и a_i0 имеют одинаковые знаки.
Определяем min{| b_i / a_is |}
                      i
Если конечного минимума нет, то задача не имеет конечного оптимума (Fmax = ) Если минимум конечен, то выбираем строку q, на которой он достигается (любую, если их несколько), и называем ее разрешающей строкой. На пересечении разрешающих строки и столбца находится разрешающий элемент a_qs
V. Переходим к следующей таблице по правилам:
а) в левом столбце записываем новый базис: вместо основной переменной x_q - переменную х_s
б) в столбцах, соответствующих основным переменным, проставляем нули и единицы: 1 - против "своей" основной переменной, 0 - против " чужой" основной переменной, 0 - в последней строке для всех основных переменных;
в) новую строку с номером q получаем из старой делением на разрешающий элемент a_qs,
г) все остальные элементы a'_ij вычисляем по правилу прямоугольника:
a'_ij = a_ij - (a_is a_qj )/ a_qs
b'_i = b_i -(a_is b_q )/ a_qs

Рис. 5.4

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

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

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

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [В начало страницы]