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

  • 26 мая 2011 г.
  • 5678 Слова
Содержание
Введение 4
1 Теоретическая часть 5
1.1 Математическая постановка задачи линейного программирования 5
1.2 Симплексный метод решения задач линейного программирования 7
1.3 Двойственная задача 13
1.4 Метод искусственного базиса 17
2 Практическая часть 20
2.1 Решение задачи линейного программирования симплекс – методом 20
2.2 Решениедвойственной задачи симплекс – методом 24
2.3 Решение задачи линейного программирования методом искусственного базиса 29
Заключение 33
Список используемой литературы 34

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

представляют собой равенства, то задача линейного программирования записана в канонической форме.
Но геометрическая интерпретация, которой мы пользовались прирешении задач линейного программирования (ЛП), перестает быть пригодной для этой цели при числе свободных переменных n – m >= 3. Для нахождения решения задачи ЛП в общем случае (при произвольном числе свободных переменных) применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод. Симплекс-метод реализует упорядоченный процесс, прикотором, начиная с некоторой исходной допустимой угловой точки, осуществляются последовательные переходы от одной допустимой экстремальной точки к другой, пока не будет найдена точка оптимального решения.
Цель работы: изучить теоретические основы и научиться применять на практике симплекс – метод для решения прямой и двойственной задачи линейного программирования, а также применять метод искусственногобазиса.
Теоретическая часть
1.1 Математическая постановка задачи линейного программирования
В задачах линейного программирования целевая функция линейна, а условия-ограничения содержат линейные равенства и линейные неравенства. Переменные могут быть подчинены или не подчинены требованию неотрицательности. Одна и та же задача линейного программирования может быть записана в различной форме. Есливсе ограничения имеют вид неравенств, то задача записана в стандартной форме. Если все ее ограничения, кроме

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

Ограничения:
1. Правые части всех ограничений должны быть неотрицательными bi 0, i =1, m. Если какой-нибудь из коэффициентов bi < 0, тонеобходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;
2. Все ограничения должны быть представлены в виде равенств, поэтому при переходе от неравенства к равенству используют аппарат дополнительных переменных.
Если исходные ограничения определяют расход некоторого ресурса (знак " "), то переменные xj 0, j =n+1, k следуетинтерпретировать как остаток, или неиспользованную часть ресурса. В этом случае xj – остаточная переменная и вводится в уравнение со знаком "+".
Если исходные ограничения определяют избыток некоторого ресурса (знак " "), то вводится избыточная переменная xj 0, j =k+1, N знаком "-".
Переменные:
Все переменные должны быть неотрицательными, т.е. xj 0, j =1, n.
Если переменная...