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