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

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

Число переменных модели = m.

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

Число независимых ограничений на единицу меньше (m+n-1), именно столько базисных переменных содержит каждый опорный план, остальные переменные являются свободными, их значения обязательно = 0, среди базисных переменных могут встретиться «0» значения в этом случае опорный план называется выраженным, если значения всех базисных значений большем чем 0, то опорный план называется невыраженным.

Решением транспортной задачи оформляется таблицами которые называются матрицами планирования.

Начинается решение задачи с первого построения опорного плана.

A=B- замкнутая.

∆_ij=C_ij

Левый угол матрицы план-я перемещается max возможный-пункт напрзапасы которого удовлетворяет используется при дальнейшем рассмотрении.

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

Переменные отвечающие пустым клеткам являются свободными их значения = 0.

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

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

Улучшение 1о опорного плана осуществляется методом потенциалов, который основывается на следующем утверждений: X^* = ( X*_ij)

Оптимальный план ТЗ, то найдутся числа U_ij = 1,m(черта над 1,m) ; V_ij = 1,n(черта над 1,n)

U_ij + V_ij = C_ij

Алгоритм.

1 шаг

Вычисление потенциалов строк и столбцов. Потенциалы находятся из условия U_ij + V_ij = C_ij – для занятых клеток.

Количество переменных (m+n)

Число потенциалов – m+n количество занятых клеток на единицу меньше,система не имеет единственного решения, полагаем u₁=0, Остальные потенциалы определяются однозначно.

2 шаг

Находим оценки свободных клеток ∆_ij=C_ij –( U_i + V_j )

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

3шаг

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

Строим контурные рамки многоуг вершина которого находится в клетке *, остальные вершины в занятых и все углы прямые, контур всегда существует и является единственным. Вершина контура расставлятеся поочередно знаками + и - , начиная со знака + в вершине звездочка.

4 шаг

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

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

Необходимым и достаточным условием ТЗ является замкнутость модели. Если A ≠ B модель называется открытой.Открытая модель сводится к замкнутой.

A= a_i = _j = B

A ≠ B (A<B) (A>B)

1. A<B СУММАРНЫЕ ЗАПАСЫ МЕНЬШЕ СУММАРНЫХ ПОТРЕБНОСТЕЙ. В этом случае вводится ??? пункт направления.

П.О: a_m+1= _j – _i

2)

A>B Суммарные запасы больше суммарных потребностей

П.О. b_n+1= _i – _j

Тарифы перевозок из фиктивного пункта напрвл в фиктивн пункты назн полагаются = 0, потому что грузы в действительности не ??? при необходимости заблокировать перевозки его какому-либо направлению, тариф перевозок =М- очень большое положительное число

.

? Многокритериальная задача принятия решения и ее математическая модель. Понятие оптимальных по Парето решений много-й задачи.

Формальная схема многокритериальной ЗЛП (МЗЛП) от обычной ЗЛП отличается наличием нескольких целевых функций:

где _i – неотрицательные переменные (невязки, i = 1; m).

З

(2)

(3)

нак max означает тот факт, что желательно увеличение каждой из линейных форм L^r(х), отражающей некоторую r-ю цель ЛРП.

Требование только максимизации не сужает общности задачи. Так, например, требование минимизации затрат некоторых ресурсов эквивалентно требованию максимизации остатка от изначально выделенных ресурсов. Наличие многих ч-критериев позволяет сделать модель (1) – (3) более адекватной изучаемой ситуации, однако выводит её из класса задач МП и требует разработки новых способов ее анализа. Начальный анализ МЗЛП состоит в удалении из области допустимых решений (ОДР) D_х явно худших, доминируемых решений х. Решение х^, доминирует решение х (х^, > х), если при х^, хотя бы один ч-критерий имеет больше значение при равенстве остальных. Поэтому решение х может быть исключено из дальнейшего рассмотрения, как явно худшее, чем х^,. Если решение х^, не доминируется ни одним из решений х  D_x, то его называют Паретто-оптимальным ( - оптимальным) или эффективным решением ( - решением). Таким образом, -решение - это неулучшаемое (недоминируемое) решение, и ясно, что решение ЛПР должно обладать этим свойством – другие решения нет смысла рассматривать.

Формальное определение -оптимальности решения х^, записывается как требование об отсутствии такого решения х D_x, при котором бы были выполнены условия

(4)

и хотя бы одно из них – строго (со знаком >).

Иными словами, условия (4) выражают требование невозможности улучшения решения х^, в пределах ОДР D_x ни по одному ч-критерию без ухудшения хотя бы по одному из других.

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

Удаление пассивных ограничений

Перед построением -множества из системы ограничений должны быть удалены пассивные ограничения. Пассивным будем называть неравенство (п-неравенство), граница которого не является частью границ области D_x, за исключением, может быть, ее отдельной точки. Неравенства, образующие границы D_x, назовем активными (а-неравенства).

Чтобы грани не были включены в D_x^, не имея никакого отношения к D_x^, неравенство ₁ должно быть удалено из исходной системы ограничений. Условием для исключения неравенства _i  0 из системы является несовместность (или вырожденность) данной системы неравенств при условии _i = 0. Геометрически это означает, что граница _i = 0 неравенства _i  0 не пересекается с областью D_x или имеет одну общую точку. Если граница _i = 0 имеет общую угловую точку с D_x (вырожденность), то с удалением п-неравенства _i  0 эта точка не будет утеряна, так как она входит в границы других неравенств. Помимо заданных m неравенств проверке подлежат и n условий неотрицательности переменных, так как координатные плоскости (оси) также могут входить в границы D_x.

В качестве примечания можно отметить, что поскольку п-неравенства (пассивные неравенства) для любой точки x  D_x будут выполнены, то по мере выявления п-неравенств и введения их в базис они удаляются из с-таблицы.

Запишем систему неравенств D_x в форме с-таблицы:

Т1	х1	х2	1	bi/ais	bi/ais
1	-1	-1	15	15	15
2	5	1	-1	1/5	1
3	1	-1	5	-	5
4	0	-1	20	-	20