Методы линейного программирования для решения транспортной задачи (стр. 2 из 6)
3. Необходимое и достаточное условия разрешимости транспортной задачи
Ограничение (1) и условия неотрицательности переменных, исключающие обратные перевозки xij>0; i= 1, 2, …, k; j= 1, 2,., l.
Эти условия образуют систему ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.
Как видим, система ограничений задана в основном (k + l) уравнениями. Установим условия, при которых эта система будет совместной, т.е. будет иметь решения.
Сложим элементы xij матрицы перевозок по строкам, каждая строка в сумме дает Mi, и в итоге получим
. Сложим те же элементы по столбцам, каждый столбец дает Nj, и в сумме получим 
. Но от перестановки слагаемых сумма не меняется, поэтому для любого допустимого плана обязательно будет выполняться условие 
.Равенство
является необходимым условием совместности ограничений задачи.Докажем и достаточность этого условия: если запасы равны потребностям, то всегда имеется допустимый план.
Действительно, пусть
. Рассмотрим такие числа: 
Убедимся, что эти числа образуют допустимый план. Для этого достаточно проверить, что они удовлетворяют всем ограничениям задачи.
Просуммируем эти числа по индексу i:
.Но величины Nj,
от индекса i не зависят и их можно вынести за знак суммы. В результате 
или
, 
Следовательно, взятые числа удовлетворяют группе уравнений (1).
Просуммируем эти числа по индексу j:
Вынося постоянные Mi и
за знак суммы и имея в виду, что , получаем 
или в развернутом виде
Как видим, наши числа удовлетворяют группе уравнений (1). Эти числа неотрицательны, т.е. система ограничений полностью удовлетворяется. Таким образом, допустимый план существует, что и требовалось доказать.
Равенство запасов потребностям есть необходимое и достаточное условие совместности и, следовательно, разрешимости транспортной задачи. [5]
4. Свойство системы ограничений транспортной задачи
Согласно теореме о структуре координат опорного плана задачи линейного программирования, в невырожденном опорном плане должно содержаться r отличных от нуля координат, где r - ранг системы ограничений
.В этой системе ограничений уравнений закрытой транспортной задачи имеется k+l-1 линейно-независимых уравнений, т.е. ранг системы ограничений равен k+l-1. [6]
5. Опорное решение транспортной задачи
Опорное решение (опорный план, базисное решение, basic solution) - одно из допустимых решений, находящихся в вершинах области допустимых решений. Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений.
При решении задачи линейного программирования можно поступить следующим образом: найти любое из таких "вершинных" решений, не обязательно оптимальное, и принять его за исходный пункт расчетов. Такое решение и будет базисным. Если окажется, что оно и оптимальное, расчет на этом закончен, если нет - последовательно проверяют, не будут ли оптимальными соседние вершинные точки. Ту из них, в которой план эффективнее, принимают снова за исходную точку и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строятся так называемый симплексный метод решения задач линейного программирования, а также ряд других способов, объединенных общим названием "методы последовательного улучшения допустимого решения (МПУ)": метод обратной матрицы, или модифицированный симплекс-метод, метод потенциалов для транспортной задачи и другие. Они отличаются друг от друга вычислительными особенностями перехода от одного базисного решения к другому, улучшенному. [2]
6. Методы построения начального опорного решения
6.1 Построение первоначального плана по способу северо-западного угла
В этом случае не обращают внимания на показатели затрат. Начав заполнение с клетки (1.1) - "северо-западного угла" таблицы, ступенями спускаются вниз до клетки (k, l), вычеркивая либо одну строку, либо один столбец. На последнем шаге вычеркиваются последняя (k-я) строка и последний (l-й) столбец. При практическом заполнении таблицы, вычеркивание строк и столбцов производится лишь мысленно.
Когда осуществляется первоначальное распределение поставок, то не ставится цель получить оптимальное распределение. Достижению этой цели служат последующие этапы решения задачи. Они заключаются в переходах к новым распределениям поставок, пока не будет найдено оптимальное распределение поставок. [4]
6.2 Построение первоначального плана по способу минимального элемента
При построении первоначального плана по способу северо-западного угла совершенно не учитываются тарифы, потому план получается весьма далеким от оптимального. Для решения задачи приходится делать много приближений (шагов).
Способ минимального элемента учитывает тарифы и потому позволяет найти план, более близкий к оптимальному.
Этот способ заключается в следующем.
1. Располагаем все клетки таблицы в очередь по мере возрастания тарифов, начиная с минимального.
линейное программирование транспортная задача
2. В клетку с минимальным тарифом записываем наибольшую возможную перевозку (исходя из запасов и потребностей), затем заполняем очередную по порядку клетку и т.д., пока не получим план. При этом должен строго соблюдаться баланс по строкам и столбцам. Пустые клетки прочеркиваем, а не заполняем нулями (чтобы было видно, что они не входят в план).
Полученный план будет ациклическим и будет состоять не более чем из k+l-1 компонент. Этот план и принимаем за исходный. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений. [5]
7. Переход от одного опорного решения к другому
Числа
и 
называют потенциалами. В распределительную таблицу добавляют строку и столбец . Потенциалы и находят из равенства 
, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, а остальные потенциалы определяются однозначно. Если известен потенциал , то 
, если известен потенциал , то 
.Обозначим
, которую называют оценкой свободных клеток. Если все оценки свободных клеток 
, то опорное решение является оптимальным. Если хотя бы одна из оценок 
, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.Наличие положительной оценки свободной клетки (
) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток - свободной.Для свободной клетки с
строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность и т.д. до тех пор, пока не получим оптимальное решение. [7]