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

Главная страница
Контакты

    Главная страница


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



страница1/9
Дата02.01.2018
Размер0,54 Mb.


  1   2   3   4   5   6   7   8   9


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

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


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

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


Реферат


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

2008


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

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

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

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

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

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




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











,

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

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

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

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

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

Переменные:

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

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

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



.

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

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

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

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

(1)

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

  1   2   3   4   5   6   7   8   9

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