Теоретическое обоснование симплекс-метода

Содержание

Введение 4

1 Теоретическое обоснование симплекс-метода 6

2 Построение математической модели 8

3 Аналитическое решение задачи симплекс-метода 14

4 Аналитическое решение взаимодвойственной задачи 17

5 Постановка задачи для составления программы 22

6 Программа на языке 23

Литература 38

Введение

Теоретическое обоснование симплекс-метода

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

Симплекс-метод решения задач линейного программирования был разработан американским математиком Джорджем Данцигом. Также большой вклад в его развитие внесли ученые Кун и Таккер, более известные своими разработками в области нелинейного программирования.

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

При этом на переменные, влияющие на значение критерия, накладываются линейные ограничения в виде уравнений или неравенств. По существу, симплекс-метод – это усовершенствованный графический метод решения задач ЛП в многомерном пространстве.

Подобно тому, как графический метод ищет оптимум в вершинах многоугольника, в симплексном методе оптимум ищется в вершинах n-мерного многогранника, называемого симплексом (на рисунке условное изображение симплекса; красным показан путь из опорной точки к точке оптимума).