ВЫСШАЯ МАТЕМАТИКА

Главная > Лекции по высшей математике > Линейное программирование > Симплекс-метод

 

Симплекс-метод

программная реализация симплекс-метода на языке Java

 

На данной странице установлена программа на языке Java (апплет), которая решает on-line (онлайн) задачу линейного программирования (ЛП) бесплатно. Для решения задачи ЛП применен симплекс-метод. Для работы апплета реализующего симплекс-метод на вашем компьютере должна быть установлена Java, ссылка для установки http://java.com/en/download/index.jsp

Для запуска апплета нанажмите на кнопку "Simplex". Если над этой строкой не видна кнопка "Simplex", то на компьютере не установлена Java.

  • После нажатия на кнопку « Simplex » выводится первое окно для ввода числа переменных и числа ограничений задачи на симплекс-метод.
  • После нажатия на кнопку « ok » выводится окно для ввода остальных данных задачи на симплекс-метод: режима отображения (десятичные дроби или обыкновенные), тип критерия задачи min или max , ввод коэффициентов целевой функции и коэффициентов системы ограничений со знаками « ≤ », « ≥ » или « = », ограничения вида хi ≥ 0 вводить не надо, симплекс-метод их учитывает в своем алгоритме .
  • После нажатия на кнопку «Решить» выводится окно с результатами решения задачи на симплекс-метод. Окно состоит из двух частей, в верхней части находится текстовое поле, содержащее описание приведения исходной задачи к канонической форме, которая используется для составления первой симплекс-таблицы. В нижней части окна в панели со вкладками расположены симплекс-таблицы каждой итерации с небольшим текстовым полем внизу с указанием разрешающего столбца, разрешающей строки и другой информации, что делает программу обучающей. Во вкладке с оптимальной (последней) таблицей в текстовом поле приведено полученное оптимальное решение задачи.

Замеченные ошибки и комментарии по работе апплета присылайте на mathelp6@gmail.com или звоните 8 962 700 77 06, за что мы будем Вам очень благодарны.

Программа М-метод скачать

Программа для решения транспортной задачи скачать

Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач . Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.

 

Симплекс-метод, решение задачи с начальным базисом

1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").

 симплекс-метод

Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:

симплекс-метод

Эта система является системой с базисом (базис s1, s2, s3, каждая из них входит только в одно уравнение системы с коэффициентом 1), x1 и x2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами:
-система ограничений должна быть системой уравнений с базисом;
-свободные члены всех уравнений в системе должны быть неотрицательны.

Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Итерация 0), т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

итерация 0

БП
x1
x2
s1
s2
s3
Решение Отношение
z
-4
-6
0
0
0
0
-
s1
2
1
1
0
0
64
64/1=64
s2
1
3
0
1
0
72
72/3=24
s3
0
1
0
0
1
20
20/1=20

Для улучшения решения перейдем к следующей итерации , получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец, т.е. переменную, которая войдет в базис на следующей итерации. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации это столбец x2 (коэффициент -6).

Затем выбирается разрешающая строка, т.е. переменная, которая выйдет из базиса на следующей итерации . Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s3 (коэффициент 20).

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации переменная x2 заменит в базисе s3. Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).

1)Вычисление строки х2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s3 таблицы "Итерация 0" будет совпадать со строкой х2 таблицы "Итерация 1". Строку x2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:

2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х2 выделены красным цветом.

3) Вычисление строки s1 таблицы "Итерация 1". На месте 1 в s1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х2 получен необходимый 0.

4) Вычисление строки s2 таблицы "Итерация 1". На месте 3 в s2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х2 получен нужный 0. Столбец х2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.

Строки таблицы «Итерация 1» получаем по следующему правилу:

Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).

Например для z-строки имеем:

Старая z-строка                                              (-4   -6   0   0   0         0)
-(-6)*Новая разрешающая строка                 -(0
  -6   0   0   -6   -120)
=Новая z-строка
                                              (-4   0   0   0   6      120).

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

итерация 1

БП
x1
x2
s1
s2
s3
Решение Отношение
z
-4
0
0
0
6
120
-
s1
2
0
1
0
-1
44
44/2=22
s2
1
0
0
1
-3
12
12/1=12
x2
0
1
0
0
1
20
-

Разрешающий столбец х1, разрешающая строка s2, s2 выходит из базиса, х1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.

итерация 2

БП
x1
x2
s1
s2
s3
Решение Отношение
z
0
0
0
4
-6
168
-
s1
0
0
1
-2
5
20
20/5=4
x1
1
0
0
1
-3
12
-
x2
0
1
0
0
1
20
20/1=20

Разрешающий столбец s3, разрешающая строка s1, s1 выходит из базиса, s3 входит в базис.

итерация 3

БП
x1
x2
s1
s2
s3
Решение Отношение
z
0
0
6/5
8/5
0
192
-
s3
0
0
1/5
-2/5
1
4
-
x1
1
0
3/5
-1/5
0
24
-
x2
0
1
-1/5
2/5
0
16
-

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x1 = 24, x2 = 16, zmax = 192.

Симплекс-метод, решение задачи с искусственным базисом

2) Решим задачу с искусственным базисом (хотя бы один знак неравенств-ограничений " ≥ " или " = ").

симплекс-метод

Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для этого введем две переменные х3 ≥ 0 и х4 ≥ 0 получим:

симплекс-метод

Система ограничений предлагает только одну допустимую базисную переменную x4, только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R1 ≥ 0 и R2 ≥ 0 Чтобы можно было примененить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R1, R2 и x4. Получили, так называемую, М-задачу:

симплекс-метод

Данная система является системой с базисом, в которой R1, R2 и x4 базисные переменные, а x1, x2 и x3 свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

итерация 0

БП
x1
x2
x3
R1
R2
x4
Решение Отношение
z
-4
-16
0
0
0
0
0
-
R1
3
4
-1
1
0
0
6
6/4=3/2
R2
1
3
0
0
1
0
3
3/3=1
x4
2
1
0
0
0
1
4
4/1=4
Оценка
-4
-7
1
-1
-1
0
-
-

В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х2, он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации переменная х2 из свободной перейдет в базисную, а переменная R2 из базисной – в свободную. Запишем следующую симплекс-таблицу:

итерация 1

БП
x1
x2
x3
R1
R2
x4
Решение Отношение
z
4/3
0
0
0
16/30
0
16
-
R1
5/3
0
-1
1
-4/3
0
2
6/5
x2
1/3
1
0
0
1/3
0
1
3
x4
5/3
0
0
0
-1/3
1
3
9/5
Оценка
-5/3
0
1
-1
4/3
0
-
-

Разрешающий столбец х1, разрешающая строка R1, R1 выходит из базиса, x1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:

итерация 2

БП
x1
x2
x3
R1
R2
x4
Решение Отношение
z
0
0
4/5
-4/5
32/5
0
72/5
-
x1
1
0
-3/5
3/5
-4/5
0
6/5
-
x2
0
1
1/5
-1/5
3/5
0
3/5
-
x4
0
0
1
-1
1
1
1
-

Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R1, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, получено оптимальное решение x1 = 6/5; x2 = 3/5; zmax = 72/5.

Особые случаи применения симплекс-метода

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

2) Если в разрешающем столбце симплекс-таблицы все коэффициенты меньше или равны нуль, то нельзя выбрать разрешающую строку, в этом случае решение неограничено.

3) Если ограничения задачи линейного программирования несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип " ≤ " с неотрицательными правыми частями, т.к. в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений использются искусственные переменные. Если задача имеет решение, то в оптимальной таблице в базисе нет искусственных переменных (Ri). Если они там есть, то задача не имеет решений.

Автор: Степанов Владимир
О авторе

МЕНЮ

Высшая математика Решение контрольных
Оплата контрольных
Вопросы по Skype
Редактор формул
Лекции
Видео-лекции
Учебники on-line
Скачать учебники
Решатели задач
О математике
Карта сайта

 

 

Copyright © 2004-2013