Симплексный метод решения задач линейного программирования алгоритм решения

Симплексный метод решения задач линейного программирования

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

Этот метод включает в себя три основные этапа:

1. Построение начального опорного плана.
2. Правило перехода к лучшему (точнее, нехудшему) решению.
3. Критерий проверки найденного решения на оптимальность.

1) Построение начального опорного плана.

Данную задачу линейного программирования необходимо сначала привести к каноническому виду; при этом правые части ограничений должны быть неотрицательными. Признаком возможности построения начального опорного плана служит наличие в каждом ограничении-равенстве с неотрицательной правой частью базисной переменной. Базисной называют плановую переменную, которая входит только в одно уравнение (а в другие не входит), и при этом имеет коэффициент, равный единице. Пусть задача линейного программирования приведена к каноническому виду, и все уравнения системы ограничений имеют свою базисную переменную. Приравняв базисные переменные к соответствующим правым частям ограничений, а остальные переменные к нулю, получим опорное или базисное решение задачи. Пример. Для данной задачи линейного программирования найти начальный опорный план (базисное решение). max Решение. Изменим знаки второго и третьего неравенств на противоположные, умножив каждое из них на –1. Система ограничений теперь будет такой: В каждом ограничении слева добавим положительную переменную , соответственно запишем канонический вид задачи: max . Переменные базисные. Приравниваем их к правым частям ограничений:Все остальные переменные – свободные, приравниваем их к нулю: Запишем теперь начальный опорный план (0; 0; 0; 0; 16; 4; 0).

2) Составление симплексных таблиц. Критерий оптимальности.

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

Базис		В			…
					…
					…
					…
…	…	…	…	…	…	…
					…
					…

Здесь приняты следующие обозначения. Столбец «Базис» – это базисные переменные. Столбец «» – это коэффициенты при базисных переменных в целевой функции. Столбец «В» – правые части ограничений; –коэффициенты при переменных в ограничениях; –коэффициенты при переменных в целевой функции. Последняя строка в таблице () – это проверочная или оценочная строка. –значение целевой функции, соответствующее построенному начальному плану. Его находят так: каждый элемент столбца умножают на соответствующий элемент столбца В и произведения складывают, т.е. . –называют оценками или симплексными разностями и находят так: элементы столбца умножают на соответствующие элементы столбца, складывают результаты и вычитают. Например, . Оценки () базисных переменных всегда равны нулю. Признак оптимальности опорного плана состоит в следующем: Опорный план будет оптимальным тогда и только тогда, когда все оценки для задачи на max и для задачи на min. Если критерии оптимальности не выполняются, то нужно перейти к нехудшему опорному плану, т.е. исключить из базиса некоторую переменную и ввести вместо нее новую из числа свободных переменных. Переменная, которую нужно ввести в базис, соответствует той оценке , которая не удовлетворяет условию оптимальности. Если таких оценок несколько, то среди них выбирают наибольшую по абсолютной величине и соответствующую ей переменную вводят в базис. Столбец с этой переменной называютразрешающим. Для определения переменной, которую нужно вывести из базиса, поступают так: элементы столбца В делят только на положительные элементы разрешающего столбца и находят симплексные отношения . Выбирают изнаименьшее. Оно называет ту переменную, которую нужно ввести в базис. Соответствующая строка таблицы называетсяразрешающей. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере. Пример. Решить симплексным методом задачу линейного программирования. max Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства. max 2) Определяем базисные переменные – это . 3) Заполняем первую таблицу

Базис		В	2	3	0	0	0	0
	0	18	1	3	1	0	0	0
	0	16	2	1	0	1	0	0
	0	5	0	1	0	0	1	0
	0	21	3	0	0	0	0	1	–
		0	–2	–3	0	0	0	0

Здесь ине удовлетворяют условию оптимальности, т. к. они меньше нуля. Выбираем среди них большее по модулю. Это. Следовательно, столбец переменной– разрешающий. Значит, в новый базис нужно ввести переменную. Находим :;; Наименьшее из этих чисел – это число 5, что соответствует строке базисной переменной . Значит, строка базисной переменной– разрешающая, следовательно, из базиса нужно вывести переменную. Элемент=1 – разрешающий. Новый базис:. Заполнение следующей таблицы начинаем со столбцов «Базис» и «». Потом заполняем разрешающую строку, разделив каждый ее элемент на разрешающий, т.е. на 1. Все элементы разрешающего столбца будут нулями, кроме разрешающего, который всегда равен 1. Столбцы подпереписываем без изменения, т. к. эти переменные остались в базисе. Остальные элементы новой таблицы находим по правилу прямоугольника. Например, элементнайдем из прямоугольника = Или элемент =из прямоугольника Оценки для новой таблицы можно находить по этому же правилу. Вцелом, решение данной задачи симплексным методом в виде таблиц будет иметь вид

Базис		В	2	3	0	0	0	0
	0	18	1	3	1	0	0	0	6
	0	16	2	1	0	1	0	0	16
	0	5	0	1	0	0	1	0	5
	0	21	3	0	0	0	0	1	–
		0	–2	–3	0	0	0	0	таб. 1
	0	3	1	0	1	0	–3	0	3
	0	11	2	0	0	1	–1	0	5,5
	3	5	0	1	0	0	1	0	–
	0	21	3	0	0	0	0	1	7
		15	–2	0	0	0	3	0	таб. 2

Базис		В	2	3	0	0	0	0
	2	3	1	0	1	0	–3	0	–
	0	5	0	0	–2	1	5	0	1
	3	5	0	1	0	0	1	0	5
	0	12	0	0	–3	0	9	1
		21	0	0	2	0	–3	0	таб. 3
	2	6	1	0	–0,2	0,6	0	0
	0	1	0	0	–0,4	0,2	1	0
	3	4	0	1	0,4	–0,2	0	0
	0	3	0	0	0,6	–1,8	0	1
		24	0	0	0,8	0,6	0	0	таб. 4

Оценочная строка четвертой таблицы показывает, что получен оптимальный план, так как все. –это значения из столбца В, т.е.,,,. Свободные (небазисные) переменные . Итак, = (6; 4; 0; 0; 1; 3), = = 24. Примечание: При переходе от таблицы к таблице для контроля сравнивают , которое должно быть не меньше предыдущего для задачи на максимум и не больше предыдущего – для задачи на минимум. При использовании симплексного метода возможны следующие случаи. 1) Если в оценочной строке симплекс-таблицы оценка = 0 соответствует свободной переменной, то это означает, что ЗЛП имеет не единственный оптимальный план. 2) Если при переходе от одного опорного плана к другому в разрешающем столбце нет положительных элементов, то это означает, что целевая функция ЗЛП является неограниченной и оптимальных планов не существует. Задания для самостоятельной работы. Определить оптимальный план задач, используя симплексный метод решения задач линейного программирования:

а)

max

б)

min

Источник

Тема 3. Симплексный метод решения задач линейного программирования

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

В алгебраических терминах симплекс-метод предполагает:

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного плана;

3) умение переходить к нехудшему опорному плану.

Геометрический смысл симплекс-метода состоит в последовательном переходе от одной вершины многогранника ОДР к соседней, в которой целевая функция принимает лучшее значение, до тех пор, пока не будет найдено оптимальное решение.

Симплексный метод универсален, поскольку позволяет решить любую ЗЛП.

2. Критерий оптимальности решения злп

Для использования симплекс-метода ЗЛП должна быть приведена к каноническому виду с предпочтительными переменными.

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

В ходе решения ЗЛП могут возникнуть 4 случая:

1) , следовательно, план не оптимален и используется основной симплекс-метод;

2) , следовательно, план не оптимален и применяется двойственный симплекс-метод;

3) , следовательно, план не оптимален и применяется смешанный симплекс-метод;

4) , следовательно, согласно критерию оптимальности, план оптимален.

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

1) Записать математическую модель в допустимом предпочтительном виде канонической формы.

2) Составить нулевую итерацию, записав математическую модель ЗЛП в первую симплекс-таблицу и взяв в качестве базисных переменных предпочтительные.

3) При наличии отрицательных коэффициентов целевой функции с_j осуществить подготовку к переходу к новому решению по следующей схеме:

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

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

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

4) Заполнить следующую симплекс-таблицу:

а) базисную переменную (б.п.) в разрешающей строке заменить на переменную разрешающего столбца, все остальные переменные оставить в неизменном порядке;

б) заполнить столбцы базисных переменных: на пересечении столбца и строки базисной переменной поставить 1, остальные элементы столбца приравнять нулю;

в) если в разрешающем столбце прежней таблицы есть 0, то соответствующую ему строку переписать без изменений;

г) если в разрешающей строке прежней таблицы есть 0, то соответствующий ему столбец переписать без изменений;

д) построить опорную строку (·) в новой таблице, разделив все элементы разрешающей строки прежней таблицы на разрешающий элемент;

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

5) Целевая функция в новой таблице проверяется на оптимальность: если при реальных переменных, то получен оптимальный план решения ЗЛП, а если среди с_j есть отрицательный коэффициент, то перейти к пункту 2 алгоритма.

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

Число единиц ресурсов, затрачиваемых на изготовление единицы продукции

Источник