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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2.1)

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

(2.2)

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

(2.3)

где

(2.4)

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

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

Пример геометрического представления  области допустимых решений задачи, где F - линия целевой функции, F=0 начальное положение функции, F=Fmax оптимальное положение функции, A, B, C, D, E - вершины многоугольника. (2.5)

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

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

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

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

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

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

(2.6)

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

(2.7)

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

(2.8)

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

(2.9)

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

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

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

(2.10)

Второе базисное решение  так же допустимо и равно X₂=(0; 5; 3; 11; 0; 21) . Теперь, надо выразить функцию через неосновные переменные.

(2.11)

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

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

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

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

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

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

2.3. Двойственные задачи

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

Экономическая интерпретация  двойственных задач.

Каждой задаче линейного  программирования соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. Теория двойственности оказалась полезной для проведения качественных исследований задач линейного программирования.

Экономическая интерпретация  задачи, двойственной задаче об использовании  ресурсов. 
Ранее рассмотрена задача об использовании ресурсов (экономико-математическая модель и содержательная интерпретация этой задачи I представлены в левой части табл. 6.1). В приведенной модели b_i (i = 1, 2, ..., m) обозначает запас ресурса S_i , a_ij - число единиц ресурса S_i потребляемого при производстве единицы продукции P_j(j = 1, 2, ..., n); C_j - прибыль (выручка) от реализации единицы продукции Pj (или цена продукции Pj). 
Предположим, что некоторая организация решила закупить ресурсы S₁, S₂, ..., S_m предприятия и необходимо установить оптимальные цены на эти ресурсы у₁, у₂, ..., y_m 
Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах b₁, b₂, ..., b_m по ценам соответственно у₁, у₂, ..., y_m были минимальны, т.е 
Z = b₁у₁ + b₂ у₂ + ... + b_m у_m min . 
С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции Р₁ расходуется a₁₁ единиц ресурса S₁, a₂₁ единиц ресурса S₂, ..., a_i1 единиц ресурса S_i ..., а_m1 единиц ресурса S_m по цене соответственно у₁, у₂, ..., у_i ..., y_m. Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции Р₁ должны быть не менее ее цены c₁, т.е. 
a₁₁ у₁ + a₂₁ у₂ +:+ a_m1 у_m>= c₁  
Аналогично можно составить ограничения в виде неравенств по каждому виду продукции Р₁, Р₂, ..., Р_m. Экономико-математическая модель и содержательная интерпретация полученной таким образом двойственной задачи II приведены в правой части табл. 6.1.

Задача I (исходная)

Задача II (двойственная)

F=c1x1+c2x 2+...+cnxn max                              (6.1)  при ограничениях  a11x1 + a12x2+...+ a1nxn <= b1  a21x1 + a22x2+...+ a 2nxn <= b2                                (6.2)   am1x1 + am2x2+...+ amnxn <= bm  и условии неотрицательности  x1>= 0; x2>= 0;: xn>= 0  Составить такой план выпуска продукции   Х = (х1, х2, ..., хn),  при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Z=b1y1+b2y2+...+bm ym min                              (6.4)  при ограничениях  a11у1 + a21у2+...+ am1уm >= c1  a12у1 + a22у2+...+ am2уm >= c2                                (6.5)  a1nу1 + a2nу2+...+ amnуm >= cn  и условии неотрицательности.  y1>= 0; y2>= 0;: ym>= 0  Найти такой набор цен (оценок) ресурсов  Y = (у1, y2, ..., уm),  при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

Цены ресурсов у₁, у₂, ..., у_m в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, "ненастоящие" цены. В отличие от "внешних" цен c₁, с₂, ..., c_n на продукцию, известных, как правило, до начала производства, цены ресурсов у₁, у₂, ..., у_n являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.

Свойства двойственных задач.

Рассмотрим формально  две задачи I и II линейного программирования, представленные в табл. 6.1, абстрагируясь от содержательной интерпретации параметров, входящих в их экономико-математические модели. Обе задачи обладают следующими свойствами: 
1. В одной задаче ищут максимум линейной функции, в другой - минимум. 
2. Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой. 
3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида "<=", а в задаче минимизации - все неравенства вида ">=". 
4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:  
для задачи I A =