Реализация модифицированного симплекс-метода

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

Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что  
а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n 
б) область G определяется системой линейных равенств или неравенств.

Математическая модель любой  задачи линейного программирования включает в себя:

• максимум или минимум целевой функции (критерий оптимальности);
• систему ограничений в форме линейных уравнений и неравенств;
• требование неотрицательности переменных.

Пример 2.1.1

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

	(2.4)
	(2.5)
	(2.6)

Коэффициенты a_i,j, b_i, c_j, j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0).

Итак, решения, удовлетворяющие  системе ограничений (2.4) условий  задачи и требованиям неотрицательности (2.5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными.

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

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁, х₂, ..., х_n являются неотрицательными:

	(2.7)
	(2.8)
	(2.9)

К канонической форме можно  преобразовать любую задачу линейного  программирования.

Правило приведения ЗЛП к  каноническому виду:

1. Если в исходной задаче  некоторое ограничение (например, первое) было неравенством, то оно  преобразуется в равенство, введением  в левую часть некоторой неотрицательной  переменной, при чем в неравенства  «≤» вводится дополнительная  неотрицательная переменная со  знаком «+»; в случаи неравенства  «≥» - со знаком «-»

(2.10)

Вводим переменную

.

Тогда неравенство (2.10) запишется  в виде:

(2.11)

В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.

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

, l - свободный индекс

3. Если в ограничениях  правая часть отрицательна, то  следует умножить это ограничение  на (-1)

4. Наконец, если исходная  задача была задачей на минимум,  то введением новой целевой  функции F₁ = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁.

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

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений  ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны.

	(2.12)

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

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

 

2. Теоремы линейного программирования

 

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

Теорема 1.1. Если целевая  функция f принимает максимальное значение в некоторой точке множества  допустимых планов D, то она принимает  это значение и в некоторой  угловой точке данного множества.

Доказательство.

Чтобы не усложнять изложение, ограничимся тем случаем, когда  множество D ограничено, и, следовательно, является выпуклым многогранником.

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

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

* Строгое доказательство  данного утверждения см., например:

Пусть х1, х2,…,хm — угловые точки множества D, а х* — точка, в которой целевая функция f достигает максимума.

На основе сформулированного  выше утверждения точку х* можно представить в виде выпуклой комбинации угловых точек х1, х2,..., xm

Так как х* — точка максимума, то для любого х D сх* ≥ сх. Функция f(x) — линейная, поэтому

следовательно,

где xr — угловая точка, удовлетворяющая условию

Из (1.10) видно, что сх* ≤ схr. В то же время справедливо обратное неравенство: сх* ≥ схr. Откуда следует, что сх* = схr, т. е. существует по крайней мере одна угловая точка хr, в которой целевая функция принимает максимальное значение. A

 

3. Определение начального допустимого решения

 

Для сбалансированной транспортной задачи существует только m + n - 1 независимых  уравнений. Таким образом, начальное  базисное допустимое решение должно иметь m+n-1 базисных переменных.

Начальное базисное решение  транспортной задачи получают непосредственно  из транспортной таблицы. Для этого  можно использовать три процедуры.

 

3.1 Метод северо-западного  угла

 

При нахождении опорного плана  транспортной задачи методом "северо-западного  угла" на каждом шаге рассматривают  первый из оставшихся пунктов отправления  и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или  по столбцу вниз (увеличение i, увеличение j). Переменной Х11 приписывают максимальное значение, допускаемое ограничениями  на спрос и запасы.

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

Исходный опорный план, построенный по правилу "северо-западного  угла", обычно оказывается весьма далеким от оптимального, так как  при его формировании не учитывается  стоимость перевозок (величина сij). Более совершенным правилом является правило "минимального элемента".

 

3.2 Метод минимальной стоимости 

 

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

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

 

3.3 Метод потенциала 

 

Этот первый точный метод  решения транспортной задачи предложен  в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).       

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

Составим двойственную задачу

1.  ,   - любые

2.     

3. 

Пусть есть план  

Теорема (критерий оптимальности): Для того чтобы допустимый план перевозок   в транспортной задаче был оптимальным, необходимо и достаточно, чтобы существовали такие числа  ,   , что                            

 если  ,                         (6)                            

 если  .                         (7)

числа   и     называются потенциалами пунктов отправления   и назначения   соответственно.

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

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

Процесс улучшения плана  продолжается до тех пор, пока не будут  выполнены условия (7). 

 

3.4 Метод Фогеля 

 

Метод Фогеля (англ. Vogel’s approximation method) — один из методов получения начального решения транспортной задачи. В отличие отметода северо-западного угла или метода минимальных тарифов, генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи метода потенциалов.

Метод Фогеля состоит в  вычислении для каждой строки транспортной таблицы разницы между двумя  наименьшими тарифами. Аналогичное  действие выполняют для каждого  столбца этой таблицы. Наибольшая разница  между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько  строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку.^[2]:115Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы (в примерах ниже они закрашиваются серым цветом), и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых («серых») ячеек.