Государственное образовательное учреждение высшего
профессионального образования
"Московский государственный технический университет им. Н.Э. Баумана"
Калужский филиал
Реферат
"Решение задачи линейного программирования симплекс-методом"
2008
Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования
Теоретическая часть.
Математическая постановка задачи линейного программирования.
Из практики рассмотрения задач математического программирования следует, что в общем виде решить их практически невозможно. Целесообразно рассматривать отдельные классы (виды) задач. Для каждого такого класса удается сформулировать алгоритм решения, приемлемый только для данного класса задач. Наиболее разработанными в математическом программировании являются задачи линейного программирования (ЛП).
В задачах линейного программирования целевая функция линейна, а условия-ограничения содержат линейные равенства и линейные неравенства. Переменные могут быть подчинены или не подчинены требованию неотрицательности. Одна и та же задача линейного программирования может быть записана в различной форме. Если все ограничения имеют вид неравенств, то задача записана в стандартной форме. Если все ее ограничения, кроме
представляют собой равенства, то задача линейного программирования записана в канонической форме.
Ограничения:
1. Правые части всех ограничений должны быть неотрицательными
2. Все ограничения должны быть представлены в виде равенств, поэтому при переходе от неравенства к равенству используют аппарат дополнительных переменных.
Если исходные ограничения определяют расход некоторого ресурса (знак "
Если исходные ограничения определяют избыток некоторого ресурса (знак "
Переменные:
Все переменные должны быть неотрицательными, т.е.
Если переменная не имеет ограничения в знаке, то её нужно представить как разность двух неотрицательных переменных:
Если такая переменная попадает в оптимальное решение, то
Целевая функция:
Подлежит максимизации или минимизации.
Система ограничений в виде равенств и неравенств образует выпуклое множество - выпуклый многогранник. Это множество может быть ограниченным и неограниченным. Целевая функция задачи линейного программирования также является выпуклой функцией. Таким образом, задача линейного программирования является частным случаем задачи выпуклого программирования.
Рассмотрим систему ограничений задачи линейного программирования в виде равенств
Система (1) линейных уравнений совместна, если она имеет, по крайней мере, одно решение. Система (1) называется избыточной, если одно из уравнений можно выразить в виде линейной комбинации остальных.
В системе (1) число переменных (неизвестных
Целевая функция задачи линейного программирования есть уравнение плоскости (или гиперплоскости для числа переменных больше трех). Максимальное или минимальное значение целевая функция задачи линейного программирования достигает либо в вершине выпуклого многогранника, либо на одной из его граней. Таким образом, решение (решения) задачи линейного программирования лежит в вершинах выпуклого многогранника и для его нахождения надо вычислить значения целевой функции в вершинах выпуклого многогранника, определяемого условиями-ограничениями задачи.
Решение задачи линейного программирования графическим методом.
Трудность построения математической модели заключается в идентификации переменных и последующем представлении цели и ограничений в виде математических функций этих переменных. Если модель содержит только две переменные, то задачу линейного программирования можно решить графически. В случае трёх переменных графическое решение становится менее наглядным, а при большем значении переменных – даже невозможным. Однако графическое решение позволяет сделать выводы, которые служат основой для разработки общего метода решения задачи линейного программирования.
Первый шаг при использовании графического метода заключается в геометрическом представлении допустимых решений, т.е. построении области допустимых решений (ОДР.), в которой одновременно удовлетворяются все ограничения модели. При получении графического решения переменная