Министерство  связи и транспорта

Ставропольский  колледж связи  имени В. А. Петрова 
 
 
 

Курсовая  работа по предмету:

«Математическое моделирование» 
 

 

Реализация  симплекс-метода в случае отрицательных  свободных членов 
 
 
 
 
 
 

Выполнил  студент группы ПОВ-20/4

-. 

Проверил  преподаватель

Тышляр  Евгений Игоревич. 
 
 
 
 
 
 

Ставрополь, 2004г.

Содержание

Введение

         Линейное  программирование сейчас широко используется в экономике, для решения производственных задач, выбора стратегии управления различными экономическими процессами и для другого. Поэтому решение  подобных задач весьма актуально на сегодняшний день.

         Но  целью данной работы является не столько  решение задач линейного программирования, сколько реализация этого решения  с помощью ЭВМ. Конкретно, в этой работе разбирается реализация симплексного метода решения и поиска первоначального допустимого базисного решения.

         Прилагающаяся к работе программа имеет цель научить пользователя на примере  решать задачи линейного программирования с помощью симплексных таблиц. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

 
 

         В этом разделе работы кратко излагается теория решения задач линейного программирования симплексным методом, поиск первоначального допустимого решения, использование симплексных таблиц. Знание данных аспектов необходимо для их машинной реализации, а значит проведения опытно-экспериментальной части данного курсового проекта.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Задачи  линейного программирования

 

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

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

         Экономико-математическая модель - это математическое описание экономического процесса или объекта. Такие модели используются для исследований и анализа экономических процессов. Реализуя их обработку на ЭВМ, мы получаем выигрыш во времени и средствах, так как проведение опытов, как правило, более трудоёмкий и дорогостоящий процесс, кроме того, не всегда возможный. Не буду здесь вдаваться в теорию моделирования, скажу лишь, что именно реализация исследования экономических процессов с помощью ЭВМ для нас и представляет интерес, а проявляется это в машинном решении задач линейного программирования, которые в свою очередь и являются экономико-математическими моделями.

         Все задачи линейного программирования можно разделить на следующие  группы:

• Задачи об использовании ресурсов, сырья, планирования производства
• Задачи составления рациона
• Задачи об использовании мощностей, загрузке оборудования
• Задачи о раскрое материалов
• Транспортные задачи

         Их  рассмотрение здесь не приведено, так  как не является необходимым для данного проекта.

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

         Дана  система из m линейных уравнений  и неравенств с n переменными:

         и линейная функция 

         Необходимо  найти такое решение (план) системы 

         где

         при котором линейная функция F (2.2) принимает оптимальное), есть максимальное или минимальное в зависимости от задачи) значение. При этом система (2.1) - система ограничений, а функция F (2.2) - целевая функция (функция цели).

         Геометрически область допустимых решений такой задачи можно представить как многогранник в n мерном пространстве (2.5).

         Причём, как правило, оптимальное решение  это одна из его вершин. А поиск  оптимума выражается в переходе от одной вершины к другой и выборе оптимальной. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Решение задач симплексным  методом

 

         В основе симплексного метода лежит перебор вершин многогранника области допустимых решений с учётом изменений функции цели. То есть при переходе от одной вершине к другой надо, чтобы функция цели принимала лучшее (или не худшее) значение, чем на предыдущем шаге. Тем самым число перебираемых вершин сокращается, и оптимум находится быстрее.  

         Для решения задач симплексным методом  надо освоить три основных элемента:

• способ определения первоначального допустимого базисного решения
• правило перехода к лучшему решению
• критерий проверки оптимальности найденного решения

 

         Кроме того, для решения задачи симплексным  методом, она должна быть представлена в канонической форме (все неравенства  должны быть заменены уравнениями). Для  этого, если в неравенстве стоит  знак " " или " ", надо ввести дополнительную переменную в левую часть уравнения, со знаком "-" при её коэффициенте, иначе со знаком "+". И так заменяются все неравенства. 
Далее, на примере, показано как ищется оптимум в симплексной задаче, в алгебраическом виде.  
Дана следующая функция цели:

         при ограничениях

         Надо  найти максимум в этой задачи. 
Сначала надо с помощью дополнительных переменных привести задачу к каноническому виду:

         Далее надо выбрать m - 4 основных переменных. Они выбираются по следующему правилу: каждая из этих переменных должна входить  в какое-либо уравнение один раз, при этом не должно быть такого уравнения, где не было бы ни одной из них (определитель этих переменных не должен быть нулевым). Исходя из этого правила, нам подходят x3, x4, x5, x6. Так как их знаки совпадают со знаком соответствующего свободного члена уравнения, то данное решение системы является допустимым, иначе надо искать первоначальное допустимое решение (смотрите следующий подраздел). Далее выражаем основные переменные через неосновные.

         Первое полученное решение выглядит как X1=(0,0,18,16,5,21) - цифры  это свободные члены в уравнении, где находится основная переменная (все переменные идут по порядку), если данная переменная неосновная, то пишем ноль. Так как в этом решении нет отрицательных компонент оно допустимо, о чём говорилось ранее. Но, глядя на функцию цели (2.6) мы видим, что в ней есть положительные переменные, а значит, её значение можно увеличить (за счёт любой из них). Выбираем для её увеличения, например, x2.

         Сперва, надо определить границу роста этой переменной в каждом уравнении, при  этом надо следовать следующим правилам:

• если переменной нет в уравнении, то граница роста равна бесконечности
• если свободный член и коэффициент при этой переменной в уравнении имеют одинаковый знак, то граница так же равна бесконечности
• если свободный член отсутствует, а коэффициент больше или равен нулю, то граница так же равна бесконечности
• иначе (знаки при свободном члене и коэффициенте при переменной разные) граница равна частному от деления свободного члена на коэффициент при переменной

 

         В данном примере получаем: x2=min{18/3; 16/1; 5/1; ?}=5, выбирается самая маленькая граница, она и определяет разрешающее уравнение. В данном случае это третье уравнение. Теперь в разрешающем уравнении переводим x2 в основные переменные (а значит x5 в дополнительные). И выражаем x2 во всех уравнениях через его значение (уравнение).

    Второе  базисное решение так же допустимо  и равно X2=(0; 5; 3; 11; 0; 21) .

    Теперь, надо выразить функцию через неосновные переменные.

         Как видите, есть ещё  положительная переменная x1, а значит, текущее значение функции (F=15) можно увеличить. Повторяем все шаги, в итоге у вас должно получится значение 24. Из вышесказанного можно сделать вывод, что максимум функции цели достигнут тогда, когда в её уравнении нет ни одной положительной переменной, для минимума наоборот (задача на минимум решается так же, но надо убирать не положительные, а отрицательные переменные из уравнения функции).

         Вот так выглядит решение задачи симплексным методом. Но есть особые случаи симплексного метода.

         Неединственность  оптимального решения (альтернативный оптимум). Она появляется, когда после выражения функции через неосновные переменные одна из переменных становится нулевой, а другая удовлетворяет условию оптимальности. То есть оптимум найден, но можно менять нулевую переменную, хотя улучшения функции это не даст. Графически это представляется как совпадение линии функции с линией многогранника области допустимых решений.

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

         Отсутствие  конечного оптимума. Это когда на очередном шаге решения все границы роста равны бесконечности или минус бесконечности. Графически это выглядит, как отсутствие какое-то стороны многогранника области допустимых решений и функция может двигаться в эту сторону до бесконечности.

         Эти особые случаи тоже надо учитывать при поиске оптимума в симплексной задаче.