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

  • Просмотров 306
  • Скачиваний 9
  • Размер файла 179
    Кб

Государственное образовательное учреждение высшего профессионального образования "Московский государственный технический университет им. Н.Э. Баумана" Калужский филиал Реферат "Решение задачи линейного программирования симплекс-методом" 2008 Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования Теоретическая часть.

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

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

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

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