Предположение о том, что базисными являются первые m компонент плана, не является принципиальным, и указание диапазона по j от 1 до m в (2.11)-(2.15) можно заменить на указание о принадлежности к базису “jБ“.

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

2.2 Прямой алгоритм симплексного метода [1]

Пусть исходная задача приведена к канонической форме и начальный базис образует единичную матрицу. Тогда базисные компоненты опорного плана совпадают с правыми частями ограничений и коэффициенты Z_jk разложения вектора X_k по такому базису совпадают с компонентами этого вектора.

Для единообразия описания вычислительной процедуры в дальнейшем будем пользоваться т.н. симплексной таблицей вида:

В центральной части таблицы записываются коэффициенты при неизвестных в ограничениях, в столбце X - правая часть ограничений (базисные компоненты плана), в первой строке - коэффициенты линейной формы, во второй строке – переменные, входящие в целевую функцию и систему ограничений. Основное поле симплекс таблицы - коэффициенты при неизвестных в ограничениях. В первом столбце для удобства вычислений будем заносить коэффициенты линейной формы при базисных переменных, указанных во втором столбце (умножение его на столбец X (свободные члены B_i≥0) с суммированием дает значение L(X); аналогичное умножение его на столбец X_k даст Z_k). Последняя строка получается вычитанием из предыдущей строки элементов первой строки таблицы и позволяет судить об оптимальности плана.

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

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

Если такой единичной подматрицы не обнаруживается, то либо придется перебирать все подсистемы m уравнений с m неизвестными в надежде обнаружить неотрицательные решения, либо прибегнуть к методу искусственного базиса.

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

Полученная М-задача решается до получения оптимального плана.

Если в оптимальном плане М-задачи значения искусственных переменных равны нулю, то значения остальных компонент образуют оптимальный план исходной задачи.

Если в оптимальном плане М-задачи значение хотя бы одной из искусственных переменных отлично от нуля, то исходная задача не имеет ни одного плана (ее ограничения противоречивы).

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

3. МЕТОД ГОМОРИ [1]

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

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

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

Эта идея, принадлежащая Д. Данцигу и Р. Гомори, впервые была представлена в форме дополнительного ограничения:

(3.1)

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

К сожалению, для абсолютного большинства задач скорость сходимости процесса таких отсечений мала. Потому Р. Гомори предложена другая форма дополнительного ограничения. Так, если компонента плана, определяемая k-м уравнением системы ограничений, нецелочисленна, то добавляется ограничение

, (3.2)

где f_k - дробная часть компоненты плана (правой части ограничения) и f_kj - дробная часть коэффициента при X_j (целая часть числа – наибольшее целое, не превышающее это число; дробная часть числа равна разности между числом и его целой частью), S^* - новая дополнительная переменная.

Можно уменьшить объем преобразований, если руководствоваться следующими правилами:

1) выбирать в качестве базового для построения дополнительного ограничения уравнение, определяющее компоненту плана с наибольшей дробной частью;

2) для ввода в базис опорного плана расширенной задачи выбирать переменную, для которой достигается минимум из отношений абсолютных значений _j к значениям f_{k j} ;

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

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

Заметим, что для целочисленных программ может обнаружиться отсутствие целочисленных планов (противоречивость ограничений).

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

4. МАТЕМАТИЧЕСКАЯ И ТЕХНИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

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

Несмотря на то, что в поставляемом вместе с MatLAB пакете программ Optimization Toolbox имелась функция linprog реализующая решение линейных задач, было принято решение реализовывать симплекс-метод и метод Гомори не используя уже готовые решения, но максимально задействуя встроенные функции среды разработки.

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

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

Программная реализация

Программа написана на встроенном в MatLAB языке программирования. Не смотря на всю простоту языка программирования MatLAB’а стоит отметить его большую функциональность обеспечиваемую встроенными функциями и пакетами расширений Toolbox.

Отличительной особенностью разработанной программы является ее графический интерфейс (Рисунок 1), обеспечивающий максимально удобную работы и позволяющий работать с программой даже не посвященным в программирование, математику и экономику людям.

Основная часть программного кода в соответствии со своим назначением разделена на функции, которые хранятся отдельно от интерфейса и могут быть использованы пользователем по своему усмотрению, в том числе в других приложениях/программах или же могут быть вызваны через консоль MatLAB.

Рисунок 1. Графический интерфейс программы

Описание проекта

4.1 Запуск

Для запуска проекта необходимо запустить среду MatLAB и указать путь к каталогу с программой. Затем необходимо запустить графический интерфейс (Рисунок 1) для чего в консоли MatLAB’а требуется ввести guide и в открывшемся окошке (Рисунок 2) выбрать вкладку «Открыть существующий GUI» и указав путь к GUI-интерфейсу «MainSimplexForm.fig» нажать кнопку «ОК».

Рисунок 2. GUIDE - среда разработки и работы с GUI-интерфейсами MatLAB

В итоге появится макет интерфейса (Рисунок 3) для запуска которого достаточно нажать комбинацию клавиш «Ctrl+T» или зеленую стрелочку на панели под главным меню. После запуска перед вами появится полноценный графический интерфейс (Рисунок 1).