Методы линейного программирования

Затем производят аналогично (k+2)-ю итерацию.

Алгоритм  решения  задач линейного программирования методом потенциалов:

 

1.    Найти исходное опорное решение.

2.    Найти потенциалы из системы  уравнений u_i + v_j = c_ij, справедливых для занятых клеток. Так как занятых клеток (m+n-1), то система будет состоять из (m+n-1) уравнений с (m+n) неизвестными. Эта система имеет бесконечное множество решений. Для того чтобы найти частное решение системы, придадим одному из неизвестных любое числовое значение, например u₁=0, и найдем значения остальных.

Потенциалы u_i и v_j записываем в столбце и в строке, которые добавляем к таблице.

3.    Для всех свободных клеток  найти оценки Δ_ij= u_i + v_j - c_ij.

4.    Проверка решения на оптимальность.

Если  все Δij≤0, то найденное решение  оптимально.

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

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

Свойства  цикла:

1) в  цикле всего одна свободная  клетка, в которую пишем +λ;

2) если  строка или столбец участвует  в цикле, то двумя клетками +λ и -λ;

3) число  клеток цикла четно.

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

6.   Определяется λ так, чтобы одна  из занятых клеток освободилась  и чтобы оставшиеся поставки xij ≥0, т.е. λ=min ‹xij› для четных клеток цикла.

7.   Строится новая распределительная  таблица, в которой изменяются  только клетки цикла, остальные  переписываются без изменения.

8.    Переход в п. 2. 

Венгерский  метод 

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

Постановка  задачи. Предположим, что имеется n различных работ A₁, A₂,…, A_n и n механизмов B₁, B₂,…,B_n, каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма B_i при выполнении работы A_j обозначим C_ij, Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях. 

Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы:

, 

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

Введем  следующие понятия.

Нулевые элементы Z₁,Z₂,…,Z_k матрицы С  называются независимыми нулями, если для любого  строка и столбец, на пересечении которых расположен элемент Z_j, не содержат другие такие элементы Z_k. 

Две прямоугольные  матрицы С и D называются эквивалентными (C ~ D), если  для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот). 

Алгоритм  состоит из предварительного этапа  и не более чем (n-2) последовательно  проводимых итераций. Каждая итерация связана с эквивалентными преобразованиями матрицы, полученной в результате проведения предыдущей итерации, и с выбором  максимального числа независимых нулей. Окончательным результатом итерации является увеличение числа независимых нулей на единицу. Как только количество независимых нулей станет равным n, проблему выбора оказывается решенной, а оптимальный вариант назначений определяется позициями независимых нулей в последней матрице. 

Предварительный этап. Разыскивают максимальный элемент в j - м столбце и все элементы этого столбца последовательно вычитают из максимального. Эту операцию выполняют со всеми столбцами матрицы С. В результате образуется матрица с неотрицательными элементами, в каждом столбце которой имеется, по крайней мере, один нуль. 

Далее рассматривают i - ю строку полученной матрицы, разыскивают ее минимальный элемент α_i и из каждого элемента этой строки вычитают минимальный. Эту процедуру повторяют со всеми строками. В результате получим матрицу С₀ (С₀ ~ C), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования С в С₀ называется приведением матрицы. 

Находим произвольный нуль в первом столбце и отмечаем его звездочкой. Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем один за другим все столбцы матрицы С₀ и отмечаем, если возможно, следующие нули знаком  *. Очевидно, что нули матрицы С₀, отмеченные звездочкой, являются независимыми.  

(k+1)-ая итерация. Допустим, что k-я итерация уже проведена и в результате получена матрица С_k. Если в ней имеется ровно n нулей со звездочкой, то процесс решения заканчивается. В противном случае переходим к (k+1) - й итерации. 

Каждая  итерация начинается первым и заканчивается  вторым этапом. Между ними может  несколько раз проводиться пара этапов: третий - первый. Перед началом итерации знаком + выделяют столбцы матрицы С_k, которые содержат нули со звездочками. 

Первый  этап. Просматривают невыделенные столбцы С_k. Если среди них не окажется нулевых элементов, то переходят к третьему этапу. Если же невыделенный нуль матрицы С_k обнаружен, то возможен один из двух случаев: 1) строка, содержащая невыделенный нуль, содержит также и нуль со звездочкой; 2) эта строка не содержит нуля со звездочкой. 

Во втором случае переходим сразу ко второму  этапу, отметив этот нуль штрихом. 

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

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

Этот  процесс за конечное число шагов  заканчивается одним из следующих  исходов: 

1) все  нули матрицы С_k выделены, т.е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу; 

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

Второй  этап. На этом этапе строят следующую цепочку из нулей матрицы С_k: исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т.д. Итак, цепочка образуется передвижением от 0' к 0* по столбцу, от 0* к 0' по строке и т.д. 

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

Далее над элементами цепочки, стоящими на нечетных местах ( 0' ) -, ставим звездочки, уничтожая их над четными элементами ( 0* ). Затем уничтожаем все штрихи над элементами С_k и знаки выделения +. Количество независимых нулей будет увеличено на единицу. На этом (k+1) -я итерация закончена. 

Третий  этап. К этому этапу переходят после первого, если все нули матрицы С_k выделены. В таком случае среди невыделенных элементов С_k выбирают минимальный и обозначают его h (h>0). Далее вычитают h из всех элементов матрицы С_k, расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу С'_k, эквивалентную С_k. Заметим, что при таком

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

После конечного числа повторений очередной  первый этап обязательно закончится переходом на второй этап. После  его выполнения количество независимых  нулей увеличится на единицу и (k+1) - я итерация будет закончена.

     Метод полного исключения Жордана

 

    Имеется система т линейных алгебраических уравнений с п неизвестными, решение которой надо найти: 

Производят  такие преобразования, в результате которых в каждой строке и в каждом столбце матрицы системы линейных алгебраических уравнений остаются по одному неизвестному с коэффициентами, равными единице, т. е. фактически получают решение системы. Например, необходимо исключить переменную x_s из всех строк за исключением i-й. Коэффициент a_is, стоящий перед переменной x_s, называют генеральным элементом, i-ю строку и 5-й столбец — разрешающими. Прежде всего, разрешающую строку делят на a_is , и она остается без изменения. Чтобы исключить переменную x_s из первого уравнения, умножают разрешающую строку на — a_is и складывают с первой строкой. В результате получают первую строку с нулевым элементом на месте a_is. Аналогично исключают x_s в остальных строках. Получают эквивалентную запись системы алгебраических уравнений. В ней г-я строка имеет прежний вид, но все коэффициенты у нее поделены на a_is; 5-й столбец состоит из нулевых элементов (кроме единичного, стоящего в /-й строке). Остальные элементы матрицы системы и столбец свободных переменных пересчитывают по правилу прямоугольника:

     
 
 

      
 

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

Графический метод 

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

Каждое  из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством. если оптимальным решением являются координаты вершины многоугольника ОДР, значит, сколько вершин имеет ОДР, столько существует целевых функций и столько оптимальных решений по этим функциям может иметь задача. 

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

При нахождении решения задачи могут встретиться  случаи, изображенные на рис. 1 – 4: