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

  • 11 сент. 2014 г.
  • 1364 Слова
Федеральное государственное автономное
образовательное учреждение
высшего профессионального образования
«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Институт управления бизнес-процессами и экономики
Кафедра «Экономика и информационные технологии менеджмента»
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ
Симплекс-метод решения задачи линейного программирования
Преподаватель______________________ М.И. Мельдер
подпись, дата
Студент гр.ПЭ12-04 №431206405 __________________В.Г. Джанджугазян
подпись, дата
Красноярск 2014
СОДЕРЖАНИЕ
1 Цель работы 3
2Теоретическая часть 3
3 Практическая часть 4
3.1 Решение экономической задачи линейного программирования симплексным методом 4
4 Вывод 6

1 Цель работы
Рассмотреть симплекс-метод решения задач линейного программирования и научиться применять его на практике.
2 Теоретическая часть
Симплекс-метод – один из наиболее эффективных методов численного решения задач ЛП. Суть понятия «симплекс» заключается вследующем. Для тела в k-мерном пространстве симплексом называется множество, состоящее из k+1 вершин этого тела. Так, при k=2, т.е. на плоскости, симплексом будут вершины треугольника; при k=3 симплексом являются вершины четырехгранника, например тетраэдра, и т.д. Такое название методу дано по той причине, что в его основе лежит последовательный перебор вершин ОДЗП с целью определения координат той вершины, вкоторой функция цели имеет экстремальное значение.
Решение задачи с помощью симплекс-метода разбивается на два основных этапа. На первом этапе находят одно из решений, удовлетворяющее системе ограничений. Системы, в которых переменных больше, чем ограничений N> m, называются неопределенными. Они приводятся к определенным системам (N = m) путем приравнивания к нулю N-m каких-либо переменных. При этомостается система m уравнений с m неизвестными, которая имеет решение, если определитель системы отличен от нуля. В симплекс-методе вводится понятие базисных переменных, или базиса. Базисом называется любой набор из m таких переменных, что определитель, составленный из коэффициентов при этих переменных в m-ограничениях, отличен от нуля. Остальные N-m переменных называются небазисными, или свободнымипеременными. Если принять, что все небазисные переменные равны нулю, и решать систему ограничений относительно базисных переменных, то получим базисное решение.
В системе из m уравнений с N неизвестными общее число базисных решений при N> m определяется числом сочетаний
Базисное решение, в котором все xi0, i= 1, m, называется допустимым базисным решением. Таким образом, первый этап решения,используя симплекс-метод, завершается нахождением допустимого базисного решения, хотя бы и неудачного.
На втором этапе производится последовательное улучшение найденного решения. При этом осуществляется переход от одного допустимого базисного решения к другому таким образом, чтобы значение целевой функции улучшилось. Процесс решения, используя симплекс-метод, продолжается до тех пор, пока не будет достигнутонаименьшее (или наибольшее) значение функции цели. Геометрически это означает переход по ребрам из одной вершины многогранника допустимых значений в другую по направлению к той, в которой значение функции цели достигает экстремума. Симплекс-метод дает оптимальную процедуру перебора базисных решений и обеспечивает сходимость к экстремальной точке за конечное число шагов. Используя симплекс-метод, вычисленияна втором этапе ведутся по следующей схеме:
1) базисные переменные и функция цели выражаются через небазисные переменные;
2) по определенному правилу выбирается та из небазисных переменных, изменение значения которой способно улучшить значение F(x), и она вводится в базис;
3) определяется, какая из базисных переменных должна быть выведена из...