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

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

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

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

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

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

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

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

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

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

(2.1)

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

(2.2)

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

(2.3)

где

(2.4)

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

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

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

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

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

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

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

(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. Из вышесказанного можно сделать вывод, что максимум функции цели достигнут тогда, когда в её уравнении нет ни одной положительной переменной, для минимума наоборот (задача на минимум решается так же, но надо убирать не положительные, а отрицательные переменные из уравнения функции).

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

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

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

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

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

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

(2.19)

Обратите внимание, что коэффициенты при переменных в функции меняют знак! Все введённые переменные имеют тот же знак, что и свободные члены иначе надо использовать M-метод (или заранее отыскать ПДБР). Далее эти данные заносятся в первую симплексную таблицу, общий вид которой представлен ниже.

Теперь, поясним, что есть что. Каждая строка - это уравнение в расширенной системе (смотрите формулу 2.19). В столбце "Базис" перечисляются все базисные (основные) переменные, их число равно числу уравнений в системе ограничений. Следующий столбец, "Свободные член" заполняется значениями свободных членов уравнения. В самую верхнюю строку (под надписью "переменные") выписываются все переменные. Самая нижняя строка, начиная с c₁, заполняется значениями коэффициентов при переменных, которые написаны вверху таблицы, из уравнения функции (с обратным знаком, как в расширенной системе), если в уравнении функции такой переменной нет, то пишем ноль. Ячейки "a" заполняются так. Если вверху столбца написана основная переменная, то на пересечении этого столбца со строкой, в которой написана та же переменная ставим 1, во все остальные ячейки столбца пишем 0. Если же вверху столбца неосновная переменная, то в ячейки записываются её коэффициенты из соответствующего уравнения, если её нет в этом уравнении, то пишем 0. В ячейку c₀, на первом шаге просто пишем ноль.

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

Если решение не оптимально, ищем разрешающий столбец (индекс s), он определяется коэффициентом при переменной в уравнении функции, то есть нижней строкой начиная c₁. Для задачи на минимум это любой столбец, где c максимальный, положительный элемент, а для задачи на максимум, минимальный, отрицательный элемент. Далее проводим расчёт оценочных отношений и заполняем соответствующий столбец. Расчет производится в соответствии со следующим правилом:

• если b_i и a_is имеют разные знаки, то g_i равно бесконечности
• если b_i равно нулю и a_is меньше нуля, то g_i равно бесконечности
• если b_i равно нулю и a_is больше нуля, то g_i равно нулю
• если a_is равно нулю, то g_i равно бесконечности
• иначе g_i равно частному от деления b_i на a_is

После того, как столбец с g заполнен. Выбирается разрешающая строка (индекс q). Это строка, в которой самое минимальное оценочное отношение (но не ноль и не бесконечность). На пересечении разрешающих строки и столбца находится разрешающий элемент - a_qs.

Теперь составляется новая таблица. В столбце "Базис" вместо старой переменной - x_q пишем новую - x_s. Опять на пересечении основных переменных ставим 1, а остальные клетки в столбцах основных переменных заполняем нулями (включая нижнюю строку). Далее, новую строку с номером q получаем путём деления старой строки на разрешающий элемент (a_qs), при этом считаем только пустые клетки (те которые в столбцах неосновных переменных).

Остальные клетки считаем по следующим формулам:

• новая a_ij ровна старой a_ij-a_is*a_qj/a_qs
• новая b_i ровна старой b_i-a_is*b_q/a_qs
• новая c_j ровна старой c_j-c_s*a_qj/a_qs

Клетка c₀ заполняется как старая c₀-c_s*g_q.

Затем снова проверяем решение на оптимальность, если оно не оптимально ищем разрешающий элемент и так далее, пока не найдём оптимума.

Но возможны и другие ситуации - особые случаи симплексного метода. Например, задача не имеет решения, если все оценочные отношения g_i равны нулям и бесконечностям. Кроме того, задача так же может зациклится. Эти случаи тоже следует учитывать.