Государственное образовательное учреждение высшего

профессионального образования

"Московский государственный технический университет им. Н.Э. Баумана"

Калужский филиал

Реферат

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

2008

Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования

Теоретическая часть.

Математическая постановка задачи линейного программирования.

Из практики рассмотрения задач математического программирования следует, что в общем виде решить их практически невозможно. Целесообразно рассматривать отдельные классы (виды) задач. Для каждого такого класса удается сформулировать алгоритм решения, приемлемый только для данного класса задач. Наиболее разработанными в математическом программировании являются задачи линейного программирования (ЛП).

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

 

представляют собой равенства, то задача линейного программирования записана в канонической форме.

Общий вид задачи линейного программирования

,

Ограничения:

1. Правые части всех ограничений должны быть неотрицательными . Если какой-нибудь из коэффициентов < 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

2. Все ограничения должны быть представлены в виде равенств, поэтому при переходе от неравенства к равенству используют аппарат дополнительных переменных.

Если исходные ограничения определяют расход некоторого ресурса (знак ""), то переменные  следует интерпретировать как остаток, или неиспользованную часть ресурса. В этом случае – остаточная переменная и вводится в уравнение со знаком "+".

Если исходные ограничения определяют избыток некоторого ресурса (знак ""), то вводится избыточная переменная  знаком "-".

Переменные:

Все переменные должны быть неотрицательными, т.е. .

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

Если такая переменная попадает в оптимальное решение, то

.

Целевая функция:

Подлежит максимизации или минимизации.

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

Рассмотрим систему ограничений задачи линейного программирования в виде равенств

 (1)

Система (1) линейных уравнений совместна, если она имеет, по крайней мере, одно решение. ............