Добавил:
Upload
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:03 Матпрограммирование - презентации / МП Лекция 3-Симплекс-метод.pptx
X
- •Симплекс–метод
- •Оптимальное решение ЗЛП графическим методом всегда ассоциируется с угловой точкой пространства решений. Это
- •Переход от геометрического способа решения ЗЛП к симплекс-методу лежит через алгебраическое описание крайних
- •Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На
- •Процесс реализации симплекс-метода включает большое количество однотипных громоздких и утомительных вычислений. Это делает
- •Стандартная форма записи ЗЛП предполагает выполнение следующих требований:
- •Неравенства любого типа (со знаками неравенств или ) можно преобразовать в равенства путем
- •Для неравенств типа «» в левую часть неравенства вводится неотрицательная остаточная переменная.
- •Идеи, лежащие в основе графического метода решения ЗЛП, также являются основой и алгебраического
- •Мы можем увидеть пространство решений графического метода, имеющее бесконечное число точек решений, но
- •После преобразования к стандартной форме имеем следующую ЗЛП.
- •В нашем примере имеем угловых точек. Но, глядя на рисунок
- •В действительности точки Е и F также являются угловыми точками, но это недопустимые
- •Для полного перехода к алгебраическому методу решения задач ЛП необходимо как-то назвать угловые
- •В таблице перечислены все базисные и небазисные решения текущего примера.
- •Как видно из примера, при возрастании размерности задачи процесс перечисления всех угловых точек
Как видно из примера, при возрастании размерности задачи процесс перечисления всех угловых точек становится отдельной сложной задачей.
Здесь следует учесть, что ЗЛП размерности 10x20 (n=10, m=20) считаются небольшими — реальные задачи могут иметь сотни и тысячи переменных и ограничений. Однако симплекс-метод в значительной степени снимает эту проблему, поскольку он рассматривает не все возможные базисные решения (т.е. угловые точки пространства решений), а только часть
всех допустимых базисных решений. |
21 |
Соседние файлы в папке 03 Матпрограммирование - презентации