Реферат Курсовая Конспект
Симплексный метод. - раздел Социология, Задача линейного программирования и свойстваее решений Общая Идея Симплексного Метода (Метода Последовательного Улучшения Плана) Дл...
|
Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходить к нехудшему опорному плану.
Пусть ЗЛП представлена системой ограничений в каноническом виде:
.
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.
Пусть система ограничений имеет вид
Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные . Получим систему, эквивалентную исходной:
,
которая имеет предпочтительный вид
.
В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю .
Пусть далее система ограничений имеет вид
Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему
Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть (при ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные . В целевую функцию переменные , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом -М для задачи на максимум, где М - большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.
Пусть исходная ЗЛП имеет вид
(1)
(2)
(3)
причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:
(4)
(5)
, , (6)
Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет вид
Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.
Теорема.Если в оптимальном плане
(7)
М-задачи (4)-(6) все искусственные переменные , то план является оптимальным планом исходной задачи (1)-(3).
Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М-задачу, которая имеет начальный опорный план
Решение исходной задачи симплексным методом путем введения искусственных переменных называется симплексным методом с искусственным базисом.
Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные , то его первые n компоненты дают оптимальный план исходной задачи.
Теорема.Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
– Конец работы –
Эта тема принадлежит разделу:
Многие задачи с которыми приходится иметь дело в повседнев ной практике являются многовариантными Среди множе ства возможных вариантов в условиях... Математическое программирование область мате матики разрабатывающая теорию... Функцию экстремальное значение которой нужно найти в условиях экономических возможностей называют целевой...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Симплексный метод.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов