48. Общая задача линейного программирования. Транспортная задача (закрытая и открытая модель).

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

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

Такую задачу называют «основной» или «стандартной» в линейном программировании.

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

Транспортная задача

Имеется некий однородный груз, который нужно перевести с n складов на m заводов. Для каждого склада i известно, сколько в нём находится груза ai, а для каждого завода известна его потребность bj в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния cij от i-го склада до j-го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются xij — количества груза, перевезённого из i-го склада на j-й завод. Они удовлетворяют ограничениям:

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

a) суммарные запасы превышают суммарные потребности

b) суммарные потребности превышают суммарные запасы

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

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

Этапы решения

• Нахождение исходного опорного решения (либо по методу минимального тарифа или методу северо-западного угла);

• Проверка этого решения на оптимальность;

• Переход от одного опорного решения к другому (на основе метода потенциалов).

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

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

Определение. Если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+n действительных чисел , удовлетворяющих условиям для занятых клеток и для свободных клеток .

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

Условие оптимальности начального опорного решения. И если все оценки удовлетворяют условию , то опорное решение является оптимальным, а в противном случае – опорное решение не является оптимальным.

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

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

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

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 90°.

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

Для свободной клетки с положительной оценкой строится цепь, все вершины, которого кроме одной находятся в занятых клетках, углы прямые, число вершин четное. Около свободной клетки ставится знак «+», затем знаки чередуются. У вершины со знаком «-» выбирают минимальный груз, его прибавляют к грузам со знаком плюс и вычитают от грузов со знаком «-». В результате получают новое опорное решение. Это решение проверяем на оптимальность, и повторяем алгоритм получения нового опорного решения пока не получим оптимальное решение данной транспортной задачи.