ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Улучшение базисного решения ТЗЛП. Циклы пересчета

Постановка транспортной задачи линейного программирования

Определение 12.1. Транспортной задачей линейного программирования (ТЗЛП) называется задача, в которой необходимо найти оптимальный план перевозок груза от отправителей к получателям, минимизировав при этом суммарную стоимость перевозок этого груза.

Пусть имеется отправителей (поставщиков) , у которых сосредоточено количество , , …, единиц однородного продукта. Данный продукт потребляется в пунктах , , …, (назовем их потребителями). Объемы потребления , , …, единиц. Расходы на перевозку единицы продукта из пункта в пункт оцениваются величиной и приводятся в матрице транспортных расходов . Требуется составить такой план прикрепления потребителей к поставщикам (план перевозок, план поставок), при котором часть продукта вывозится из пункта в пункт в соответствии с потребностью, а суммарная стоимость всех перевозок груза (себестоимость перевозок) минимальна.

Обозначим через ( , ) количество продукта, перевозимого из пункта в пункт . Совокупность всех значений обозначим матрицей (ее называют матрицей транспортных перевозок). Тогда математическая модель ТЗЛП имеет вид

( ), (12.1)

( ), (12.2)

, (12.3)

Условия (12.1) определяют полный вывоз продукции от всех поставщиков. Условия (12.2) означают полное удовлетворение спроса во всех пунктах потребления. Условия (12.1) – (12.2) представляют собой систему линейных алгебраических уравнений с неизвестными .

Транспортная задача (12.1) – (12.3) может быть решена обычным симплекс-методом, но в силу ее особенностей для нее разработан специальный метод решения, основанный на ряде основных теорем.

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

Теорема 12.1.Для разрешимости транспортной задачи (12.1) – (12.3) необходимо и достаточно выполнение равенства (условия баланса)

. (12.4)

Определение 12.2.Транспортную задачу, в которой выполняется равенство (12.4), называют закрытой (сбалансированной). Транспортную задачу, в которой не выполняется равенство (12.4), называют открытой.

Согласно теореме 12.1, любая закрытая ТЗЛП имеет оптимальное решение. Решение открытой ТЗЛП можно свести к решению закрытой ТЗЛП.

Условия ТЗЛП (12.1) – (12.3) записываются в так называемой транспортной таблице (см. табл. 12.1).

Таблица 12.1.

			…		Запасы отправителей
			…
			…
…	…	…	…	…	…
			…
Потребности получателей			…

Для дальнейшего рассмотрения теории нам понадобится задача, двойственная к ТЗЛП (12.1) – (12.3). Обозначим переменные двойственной задачи, соответствующие уравнениям (12.1), через ( ), а переменные, соответствующие уравнениям (12.2), через ( ).

Определение 12.3.Переменные ( ) называются потенциалами отправителей, а ( ) – потенциалами получателей.

Потенциалы отправителей и получателей, как двойственные оценки ресурсов (запасов и потребностей) ТЗЛП можно интерпретировать как цены продукта в соответствующих пунктах отправителей и получателей.

Тогда задача, двойственная к ТЗЛП (12.1) – (12.3), примет вид

( , ), (12.5)

. (12.6)

Отметим, что пара задач (12.1) – (12.3) и (12.5) – (12.6) является несимметрической парой ЗЛП. Поэтому переменные ( ), ( ) задачи (12.5) – (12.6) могут принимать произвольные значения.

Так как закрытая ТЗЛП всегда имеет оптимальное решение – матрицу транспортных перевозок, то согласно первой теореме теории двойственности, соответствующая двойственная задача (12.5) – (12.6) также имеет оптимальное решение.

Из второй теоремы теории двойственности следует, что любое допустимое решение ТЗЛП (12.1) – (12.3) и допустимое решение ( ), ( ) двойственной задачи (12.5) – (12.6) будут оптимальными решениями соответствующих задач тогда и только тогда, когда они будут удовлетворять следующим условиям

( ), ( ). (12.7)

( , ). (12.8)

Отметим, что в силу равенств (12.1), (12.2) условия (12.7) выполняются при любых значениях потенциалов , . Поэтому существенными для потенциалов ( ), ( ) являются условия (12.8), которые будут использоваться в теории потенциалов.

§ 13. Построение первого базисного допустимого решения транспортной задачи линейного программирования

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

Клетки таблицы будем обозначать через .

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

Определение 13.1.В транспортной таблице поставок занятые клетки называются базисными, незанятые – свободными.

Определение 13.2. Клетку с нулевой поставкой называют условно занятой (формально занятой).

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

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

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

2) если , то необходимо занятых клеток превратить в свободные клетки. Сделать это можно при помощи циклов перерасчета (см. §15).

Пример 13.1.Составить первоначальный базисный план ТЗЛП, если запасы отправителей представлены вектором запасов , потребности получателей – вектором потребностей . Матрица транспортных расходов

Решение.Согласно алгоритму метода наименьшей стоимости, заполнение начинаем с клетки, имеющей наименьшую стоимость . В клетку помещаем поставку в объеме , в результате чего исключается получатель . Аналогично, в клетку , имеющей стоимость , помещаем поставку в объеме , в результате чего исключаем получателя . При этом, если в клетку , имеющей стоимость , поместить нулевую поставку , то мы исключим отправителя (клетка окажется формально занятой). Далее, в клетку , имеющей стоимость , помещаем поставку в объеме , в результате чего исключаем получателя . Итак, клетки со стоимостью, равной 1, оказались все занятыми.

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

Итак, первоначальный базисный план представлен в табл. 13.1.

Таблица 13.1.

					Запасы отправителей



Потребности получателей

Выпишем по табл. 13.1 матрицу транспортных перевозок

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

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

Значение целевой функции на базисном решении (суммарная стоимость перевозок груза) равна

§14. Решение транспортной задачи линейного программирования методом потенциалов

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

Согласно §12, для того, чтобы базисный план ТЗЛП (12.1) – (12.3) являлся ее оптимальным планом, необходимо и достаточно, чтобы для потенциалов ( ), ( ) и матрицы выполнялись условия (12.8). Условия (12.8) распадаются на две группы условий в соответствии со значениями переменных :

1) для базисных переменных , и поэтому из (12.8) следует, что потенциалы , должны удовлетворять условиям

; (14.1)

2) для свободных переменных условия (12.8) выполняются при любых значениях потенциалов ( ), ( ). Тогда определяющими условиями для потенциалов становятся условия (12.5)

. (14.2)

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

Следующая теорема непосредственно вытекает из проведенных выше рассуждений.

Теорема 14.1 (теорема о потенциалах). Пусть для закрытой ТЗЛП (12.1) – (12.3) составлен невырожденный базисный план . Тогда данный план является оптимальным планом ТЗЛП (12.1) – (12.3) тогда и только тогда, когда для некоторой системы потенциалов ( ), ( ) выполняются условия (14.1) – (14.2).

Сформулируем алгоритм решения ТЗЛП (12.1) – (12.3).

1) Составить невырожденный первоначальный базисный план (начальный план перевозок) методом наименьшей стоимости.

2) Поставить в соответствие -му уравнению системы (12.1) потенциал ( ), а -ому уравнению системы (12.2) потенциал ( ). Составить на основании условий (14.1) для занятых (базисных) клеток систему из уравнений с неизвестными потенциалами.

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

4) Подставляя найденные в пункте 3) значения потенциалов ( ), ( ) в (14.2), проверяем оптимальность базисного решения. Введем так называемые оценочные коэффициенты

, .

Если условия (14.2) выполняются для всех свободных клеток, то базисное решение является оптимальным. Задача решена. Заметим, что в этом случае . Если для некоторых свободных переменных :

, ,

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

Замечание 14.1. При решении ТЗЛП методом потенциалов рекомендуется составить так называемую матрицу оценок , где элементы этой матрицы удовлетворяют условию:

Тогда, если для составленного базисного плана ТЗЛП (12.1) – (12.3) все элементы матрицы оценок неположительны, то этот план является оптимальным планом. Если же в матрице оценок есть хотя бы один положительный элемента , то этот базисный план не является оптимальным и подлежит улучшению.

Пример 14.1. Проверить на оптимальность базисный план ТЗЛП, представленный в табл. 14.1, пользуясь методом потенциалов. В случае оптимальности найти минимум суммарных издержек на перевозку груза.

Таблица 14.1.

					Запасы отправителей



Потребности получателей

Выпишем по табл. 14.1 матрицу транспортных перевозок

Базисный план является невырожденным, так как , , количество занятых клеток равно ( ).

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

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

Найдем для свободных клеток оценочные коэффициенты :

свободная клетка : ,

свободная клетка : .

Составим матрицу оценок :

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

Улучшение базисного решения ТЗЛП. Циклы пересчета

Пусть составленный невырожденный план закрытой ТЗЛП (12.1) – (12.3) не является оптимальным, то есть для некоторых свободных клеток условие (14.2) не выполняется. Выпишем оценочные коэффициенты

, .

Неоптимальность базисного плана ТЗЛП (12.1) – (12.3) означает, что среди оценочных коэффициентов встречаются положительные числа.

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

Определение 15.1.Циклом пересчета, соответствующим данной свободной клетке ТЗЛП, называется замкнутая ломаная линия, одна вершина которой лежит в этой свободной клетке , а остальные вершины – в занятых (или формально занятых) базисных клетках. Данная ломаная должна удовлетворять условиям:

1) ее звенья параллельны строкам и столбцам таблицы (направление отдельных отрезков контура может быть только горизонтальным и вертикальным);

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

3) число вершин ломаной должно быть четным.

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

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

Первоначально в клетке находится нулевая поставка, а во всех остальных занятых клетках цикла пересчета положительные поставки (если план является вырожденным, то в некоторых формально занятых клетках находятся нулевые поставки). Запишем в клетку знак “+”, в соседнюю вершину знак “–”. Двигаясь вдоль цикла пересчета, будем в вершинах цикла поочередно ставить знаки “+” и “–”. Так как число вершин в цикле пересчета четно, то не важно в какую из соседних клеток совершен переход из клетки .

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

Величина подбирается таким образом, чтобы:

1) ни одна из поставок в клетке со знаком “–” не стала отрицательной;

2) поставка приняла максимально возможное значение.

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

Можно показать, что цикл пересчета позволяет уменьшить значение целевой функции (12.3) ТЗЛП на величину .

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

Пример 15.1. Решить методом потенциалов ТЗЛП, если запасы отправителей представлены вектором запасов , потребности получателей – вектором потребностей . Матрица транспортных расходов имеет вид

Решение. Транспортная задача является закрытой: .

Первоначальный базисный план, составленный по методу наименьшей стоимости, представлен в табл. 15.1.

Таблица 15.1.

					Потреб-ности



Запасы

Значение целевой функции на этом плане равно

Базисный план является невырожденным, так как , , количество занятых клеток равно ( ).

относительно неизвестных потенциалов ( ), ( ). Решение этой системы при значении имеет вид

Непосредственно убеждаемся, что для свободной клетки оценочный коэффициент положительный:

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

Цикл пересчета (см. табл. 15.1) имеет вид:

в котором является свободной клеткой, а все остальные клетки - занятые. Выпишем отдельно цикл пересчета (см. рис. 15.1) и расставим попеременное знаки, начиная со знака “+” в свободной клетке .

100 50 –– + + ––

Рис. 15.1.

Используя клетки со знаком “–”, находим поставку , которую необходимо поместить в клетку , чтобы превратить ее в занятую клетку. Соответственно клетка , из которой перемещается поставка , станет свободной клеткой. В результате получаем базисный план, представленный в табл. 15.2.

Таблица 15.2.

					Потреб-ности



Запасы

Значение целевой функции на этом плане равно

то есть в результате первой итерации (цикла пересчета) значение целевой функции уменьшили на .

Проверим базисный план, составленный в табл. 15.2., на оптимальность методом потенциалов. Решая систему

относительно потенциалов ( ), ( ), при , получим

Непосредственно убеждаемся, что теперь для свободной клетки

оценочный коэффициент положительный:

в котором является свободной клеткой, а все остальные клетки - занятые. Выпишем отдельно цикл пересчета (см. рис. 15.2) и расставим попеременное знаки, начиная со знака “+” в свободной клетке .

– +

70 130 60 – + 40 + 40 –

30 170 20 40

Рис. 15.2.

Используя свободные клетки со знаком “–”, находим поставку , которую необходимо поместить в клетку , чтобы превратить ее в занятую клетку. Соответственно клетка , из которой перемещается поставка , станет свободной клеткой. В результате получаем базисный план, представленный в табл. 15.3 (в таблицу внесены также значения потенциалов ( ), ( ) , полученных при решении соответствующей системы по занятым клеткам, при ).

Таблица 15.3.

					Потреб-ности