Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде:
F=a0,1x1+a0,2x2+…a0,nxn +b → max
a1,1x1+a1,2x2+…a1,nxn + xn+1=b1
a2,1x1+a2,2x2+…a2,nxn +xn+2 =b2
…………………………………
am,1x1+am,2x2+…am,nxn+xn+m=bm
Исходная таблица для задачи имеет следующий вид:

x1 x2 xn-1 xn b
F -a0,1 -a0,2 -a0,n-1 -a0,n -b
xn+1 a1,1 a1,2 a1,n-1 a1,n b1
xn+2 a2,1 a2,2 a2,n-1 a2,n b2
xn+m am,1 am,2 am,n-1 am,n bm

x1, x2, xn – исходные переменные, xn+1, xn+2, xn+m – дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.

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

 Подготовительный этап
Приводим задачу ЛП  к каноническому виду
F=a0,1x1+a0,2x2+…a0,nxn +b → max
a1,1x1+a1,2x2+…a1,nxn+xn+1=b1
a2,1x1+a2,2x2+…a2,nxn+xn+2=b2
…………………………………
am,1x1+am,2x2+…am,nxn+xn+m=bm
В случае если в исходной задаче необходимо найти минимум – знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком “≥” так же меняются на противоположные. В случае если условие содержит знак “≤” – коэффициенты запишутся без изменений.

 Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

Читайте также  Пример - Табличный симплекс метод
x1 x2 xn-1 xn b
F -a0,1 -a0,2 -a0,n-1 -a0,n -b
xn+1 a1,1 a1,2 a1,n-1 a1,n b1
xn+2 a2,1 a2,2 a2,n-1 a2,n b2
xn+m am,1 am,2 am,n-1 am,n bm

 Шаг 1. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю – он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l – он задает ведущий столбец – l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.
Если же среди свободных членов есть отрицательные элементы – а в соответствующей строке – нет то условия задачи несовместны и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.
Шаг 2. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b0 – текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.
Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b)

a0,l=min{a0,i }

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

Читайте также  Алгоритм Литтла - Пример 1

bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0

k – cтрока, для которой это отношение минимально – ведущая. Элемент ak,l – ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

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

    • Вместо базисной переменной xk записываем xl; вместо небазисной переменной xl записываем xk.
    • ведущий элемент заменяется на обратную величину ak,l‘= 1/ak,l
    • все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l
    • все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l
    • оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j‘= ai,j– ai,lx ak,j/ ak,l

Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.
схема прямоугольника
Преобразуемый элемент ai,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.

Пример

   
4.24
user2235229
Я Екатерина - специалист в области права и смежных наук! Имею опыт в подготовке контрольных, творческих и курсовых работ! Окажу любую помощь в выполнении ваших работ!!!

Выполненные готовые работы

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.