Краткое описание этапов решения задачи. Если план не является оптимальным, необходимо сделать перераспределение поставок в потенциальные клетки (где Uij<0) по правилу контура.

(по правилу контура)

Если план не является оптимальным, необходимо сделать перераспределение поставок в потенциальные клетки (где U _ij <0) по правилу контура.

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

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

Что является контуром и как его отыскать в плане? Контур представляет собой замкнутую фигуру, образованную прямыми отрезками, углы между которыми всегда равны 90⁰.

 

Отличительные особенности контура:

1) он состоит из четного количества вершин, которыми являются:

- загруженные поставками связи (нечетное количество);

- связь с отрицательным оценочным параметром (U_ij < 0);

2) возможные варианты контуров:

- четырехугольные: B C

B C

 

A D A D

- шестиугольные:

B C C D

 

 

E D B E

A F A F

- восьмиугольные и т.д.

Итак, используя примеры возможных контуров, определим контур в данной задаче, учитывая что одной из его вершин является связь с отрицательным оценочным параметром, а остальные вершины - загруженные поставками связи. В данном базисном плане 2 связи с отрицательным оценочным параметром - A ₂ B ₄ и A ₂ B ₄. В первую очередь должна рассматриваться связь с наименьшим оценочным параметром как наиболее потенциальная. Но в данном плане две потенциальные связи (A ₃ B ₁ и A ₂ B ₄), у которых оценочные параметры одинаковы. Они образуют два контура. Один из контуров - это четырехугольник, вершинами которого являются загруженные поставками связи A ₁ B ₁, A ₁ B ₄, A ₃ B ₄ и связь с отрицательным оценочным параметром A ₃ B ₁. Второй контур - это шестиугольник, вершинами которого являются загруженные поставками связи A ₁ B ₁, A ₁ B ₄, A ₂ B ₃, A ₄ B ₃, A ₂ B ₁ и связь с отрицательным оценочным параметром A ₂ B ₄. Для перераспределения поставок выбираем любой контур, например, второй.

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
							-1
А2
	-1
А3
А4 доп
Qj
Uj

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

А1В1 0 15 А1В4   25 А2В3 А2В4 (U ij <0)   А4В1 10 5 А4В3

Далее осуществляется перераспределение поставок по контуру: вершина с отрицательным значением оценочного параметра U _ij считается нечетной (в контуре она условно обозначается нулем - А ₂ В ₄), рядом с ней ставится знак (+), следующая за ней вершина (по часовой стрелке или против нее) принимается четной, возле нее ставится знак (-), за четной вершиной следует нечетная и т.д.:

неч.+ 0 15 чет. -   25 чет - (0) неч.+ (U ij <0)   чет.- 10 5 неч.+

Затем необходимо среди четных вершин выбрать вершину с минимальным значением объема поставки. Это значение следует вычесть из четных вершин (-) и прибавить к нечетным (+). В данном контуре:

Чет.min=10 (А₄В₁).

Это значение вычитаем из всех четных связей и прибавляем ко всем нечетным. В результате получится:

неч.+ 0+10= 10 15-10= 5 чет. -   25 -10= 15 0+10= 10 неч.+ (U i j<0) чет - чет.- 10-10= 0 5+10= 15 неч.+

Далее проверяем количество поставок: до перераспределения их было в контуре 5, значит, и после перераспределения должно остаться 5 (поэтому поставку, равную нулю (А₄В₁), из плана исключаем. Если бы оказалось несколько поставок, равных нулю, то следовало бы оставить такое их количество, при котором суммарное число поставок должно было равняться 5 и можно было бы на следующем этапе вычислить потенциалы U _i и U _j. При этом предпочтение должно отдаваться связям с наименьшими расстояниями.

Таким образом было осуществлено перераспределение поставок по контуру. С учетом этого перераспределения составим новый план закрепления постребителей за поставщиками:

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
А2
А3
А4 доп
Qj
Uj

Далее новый план закрепления потребителей за поставщиками по аналогии проверяем на оптимальность по условию:

U _ij >=0

где U _ij - оценочный параметр или критерий оптимальности базисного плана.

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

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
А2
	-1				-1
А3
А4 доп
Qj
Uj

Поскольку имеются связи, где U _ij <0, новый план закрепления потребителей за поставщиками снова признается неоптимальным:

U _ij <0: U ₃₁ = -1, U ₃₃ = -1.

Это говорит о том, что cледует еще раз произвести перераспределение поставок по контуру. Этот процесс будет осуществляться до тех пор, пока все оценочные параметры не станут положительными либо равными нулю: U _ij >=0.

Поскольку имеются две одинаково потенциальные связи с одинаковым оценочным параметром (U _ij = -1), то можно построить контур, начать рассматривать любую из них. Например, построим контур, отталкиваясь от связи А ₃ В ₁. Она образует четырехугольный контур, вершинами которого являются загруженные поставками связи - А ₁ В ₁, А ₁ В ₄, А ₃ В ₄ и связь с отрицательным оценочным параметром А ₃ В ₁ (см. таблицу выше):

чет. - 10 5 неч. +

 

неч. + 0 10 чет. -

(U _ij <0)

Чет.min=10.

Это значение необходимо вычесть из всех четных клеток и прибавить ко всем нечетным:

чет. - 10-10=0 5+10=15 неч. +

 

неч. + 0+10=10 10-10=0 чет. -

 

 

••••••••••••••••••••••

Далее проверяем количество поставок: до перераспределения их было в контуре 3, значит, и после перераспределения должно остаться 3 (поэтому поставку, равную нулю (А₄В₁), из плана исключаем. Если бы оказалось несколько поставок, равных нулю, то следовало бы оставить такое их количество, при котором суммарное число поставок должно было равняться 5 и можно было бы на следующем этапе вычислить потенциалы U _i и U _j. При этом предпочтение должно отдаваться связям с наименьшими расстояниями.

 

В соответствии с перераспределением поставок по контуру составляем новый план закрепления потребителей за поставщиками:

 

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
А2
					-1
А3
А4 доп
Qj
Uj

 

Рассчитываем необходимое количество поставок по формуле:

N=m+n-1=4+4-1=7

В данной задаче количество поставок по количеству загруженных клеток:

N=8.

По этой причине одну из условных поставок, равных по объему нулю, следует исключить из плана, например, Q ₁₁.

Далее новый план закрепления потребителей за поставщиками по аналогии проверяем на оптимальность по условию:

U _ij >=0

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

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
А2
А3
А4доп
Qj
Uj

Полученный план закрепления потребителей за поставщиками оптимален, поскольку все оценочные параметры U _ij >=0.

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

Z = (C _ij •Q _ij),

где C _ij - расстояние от i-го поставщика до j-го потребителя;

Q _ij - объем поставки от i-го поставщика к j-му потребителю.

Иными словами, чтобы рассчитать минимальные затраты на перевозку, объем поставки по каждой загруженной клетке - Q _ij необходимо умножить на соответствующее расстояние C _ij, и просуммировать все полученные произведения для всех загруженных связей (см.последнюю таблицу):

 

Z=15•6 + 15•10 +10•8 + 10•7 +20•6 + 0•8 = 510 у.е.

 

Вывод: оптимальные затраты на перевозку грузов от потребителей к поставщикам - 510 у.е.

Й вариант

Х_опт4=20 ед. (см. в табл. для i=4 во 2-й строке, какой ресурс Х₄ отмечен звездочкой *). Это будет один из оптимальных объемов ресурса на 4-м этапе.

Тогда оптимальный объем ресурса по предыдущим вариантам составит:

Х_сопт3=Х_о-Х_опт4 (5.2)

где Хо - общий объем ресурса (см. условие задачи).

Подставив данные в формулу, получим:

Х_сопт3=Х_о-Х_опт4=60-20=40 ед.

 

2) Теперь по 3-му варианту следует рассмотреть, каким оптимальным образом распределяется ресурс 40 ед., вычисленный по формуле (5.2), на предыдущем этапе i=3. Т.е. задача состоит в том, чтобы по 3-му варианту (i=3) для Х_сопт3=40ед. выделить, какой ресурс Х₃ отмечен звездочкой *, а значит, является оптимальным на 3-м этапе. В данном примере для Х_сопт3=40 ед. звездочкой на 3-м этапе отмечено три ресурса Х₃: Х₃=0 ед.; Х₃=20 ед.; Х₃=40 ед. Следовательно, на этом этапе решение многовариантно. Необходимо рассмотреть каждый вариант в отдельности.

1-а вариант	Хопт3=0 ед.
1-б вариант	Хопт3=20 ед.
1-в вариант	Хопт3=40 ед.

Теперь выясним, какой оптимальный объем ресурса остается на предыдущие варианты.

1-а вариант	Хсопт2=Хо-Хопт4 -Хопт3=60-20-0=40 ед.
1-б вариант	Хсопт2=Хо-Хопт4 -Хопт3=60-20-20=20 ед.
1-в вариант	Хсопт2=Хо-Хопт4 -Хопт3=60-20-40=0 ед.

3) Теперь по 2-му варианту следует рассмотреть, каким оптимальным образом распределяется соответствующий ресурс на предыдущем этапе i=2. Т.е. по 2-му варианту i=2 для соответствующего Х_сопт2 следует выделить, какой ресурс Х₂ отмечен звездочкой *, а значит, является оптимальным на 2-м этапе. В данном примере для Х_сопт2=40 ед. звездочкой на 2-м этапе отмечен Х₂=20 ед.; для Х_сопт2=20 ед. звездочкой на 2-м этапе отмечен Х₂=20 ед.; для Х_сопт2=0 ед. оптимальным является ресурс Х₂=0 ед.

1-а вариант	Хопт2=20 ед.
1-б вариант	Хопт2=20 ед.
1-в вариант	Хопт2=0 ед.

Затем рассчитаем оптимальный объем ресурса, который целесообразнее распределять на 1-м этапе. Сначала определим, какой оптимальный объем ресурса остается на предыдущие варианты:

1-а вариант	Хсопт1=Хо-Хопт4 -Хопт3-Хопт2=60-20-0-20=20 ед.
1-б вариант	Хсопт1=Хо-Хопт4 -Хопт3-Хопт2=60-20-20-20=0 ед.
1-в вариант	Хсопт1=Хо-Хопт4 -Хопт3-Хопт2=60-20-40-0=0 ед.

4) Для начального, 1-го, этапа имеем:

Х_опт1=Х_cопт1=40 ед.

1-а вариант	Хопт1= Хсопт1=20 ед.
1-б вариант	Хопт1= Хсопт1=0 ед.
1-в вариант	Хопт1= Хсопт1=0 ед.

 

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

А вариант

Таблица исходных данных.

Этап	Затраты при распределении ресурса Хо по вариантам
i	Х=0	Х=20	Х=40	Х=60

По 1-му варианту Х_опт1=20 ед. По таблице исходных данных видно, что по 1-му варианту при распределении 20 ед. полученный эффект составляет 5. По 2-му варианту Х_опт2=20 ед. По таблице исходных данных по 2-му варианту при распределении 20 ед. достигается эффект 6. По 3-му варианту Х_опт3=0 ед., а F₃(X₃)=0. По 4-му варианту Х_опт4=20 ед., а F₄(X₄)=7. Последовательно суммируя все эффекты, получаем общий максимальный эффект:

Z=5+6+0+7=18.

Вывод 1-а: суммарный максимальный эффект при распределении общего объема ресурса - 18.

Б вариант

Таблица исходных данных.

Этап	Затраты при распределении ресурса Хо по вариантам
i	Х=0	Х=20	Х=40	Х=60

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

Z=0+6+5+7=18.

Вывод 1-б: суммарный максимальный эффект при распределении общего объема ресурса - 18.

В вариант

Таблица исходных данных.

Этап	Затраты при распределении ресурса Хо по вариантам
i	Х=0	Х=20	Х=40	Х=60

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

Z=0+0+11+7=18.

Вывод 1-в: суммарный максимальный эффект при распределении общего объема ресурса - 18.

 

Поскольку на 4-м этапе было выделено два ресурса Х₄, отмеченых звездочкой * (Х_опт=20 ед. и Х_опт4=60 ед.), необходимо определить оптимальное решение и по 2-му варианту.

Й вариант

1) Х_опт4=60 ед. Это будет второй оптимальный вариант распределения ресурса на 4-м этапе. Он равен общему объему распределения ресурса Х_о,

Тогда оптимальный объем ресурса по предыдущим вариантам составит:

Х_сопт3=Х_о-Х_опт4=60-60=0 ед. (2)

Следовательно оптимальные решения по первым трем этапам будут равны нулю.

2) Х_опт3=0 ед.

3) Х_опт2=0 ед.

4) Х_опт1=0 ед.

 

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

Таблица исходных данных.

Этап	Затраты при распределении ресурса Хо по вариантам
i	Х=0	Х=20	Х=40	Х=60

По 1-му варианту Х_опт1=0 ед. По таблице исходных данных видно, что по 1-му варианту при распределении 0 ед. полученный эффект составляет 0. По 2-му и 3-му вариантам аналогично: Х_опт2=0 ед. и Х_опт3=0 ед., а значит, F₂(X₂)=0 и F₃(X₃)=0. По 4-му варианту Х_опт4=60 ед., а F₄(X₄)=18. Последовательно суммируя все эффекты, получаем общий максимальный эффект:

Z=0+0+0+18=18.

Вывод 2: суммарный максимальный эффект при распределении общего объема ресурса - 18.

 

Пример решения задачи № 2

 

Решить графическим методом задачу линейного программирования при ограничениях: Х₁+0,5Х₂<=3,5

0,4Х₁+Х₂<=1,5

и целевой функции Z=0,5Х₁+0,3Х₂=мах.

Краткое описание этапов решения задачи.

1) Необходимо построить две заданные прямые ограничений.

2) Эти прямые отсекают в положительной плоскости выпуклый четырехугольник АВСD. Следует определить координаты точек А, В, С и D.

3) Поскольку построенные прямые - это прямые ограничений, то они отсекают в положительной плоскости т.н. "запрещенную " область, т.е. область, не соответствующую заданным ограничениям. Эта область может находиться либо внутри выпуклого четырехугольника, либо снаружи его (и ни как иначе). О том, каким образом ее определить, будет рассказано в разделе "Подробное описание задачи".

4) Затем строится график целевой функции: Z=С₁•Х₁+С₂•Х₂=мах. Для построения графика следует приравнять С₁•Х₁+С₂•Х₂ к числу, кратному С₁ и С₂.

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

6) Графический способ решения задачи требуется подтвердить расчетным, при котором координаты каждой из вершин четырехугольника подставляются в уравнение целевой функции. Таким образом находятся значения целевой функции в каждой из точек: Z_A, Z_B, Z_C и Z_D. При решении задачи на максимум, как в данном примере, оптимум будет в той точке, в которой значение целевой функции максимально.