Разработка динамических моделей для транспортно-производственной системы (стр. 3 из 5)

Требуется найти такие объемы транспортировки продукции от каждого поставщика к каждому потребителю ( x_i_,_j > 0, для i = N и j = M) ), при которых достигается минимум транспортных затрат (что при фиксированных ценах реализации продукции равносильно максимизации прибыли), то есть:

(1.1)

При этом должны соблюдаться условия:

- продукции должно быть вывезено не более произведенного количества:

(1.2)

- платежеспособный спрос должен покрываться:

(1.3)

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

Во-первых, разность оценок пунктов потребления ( v_j) и производства ( u_i), между которым запланированы перевозки, равна затратам на транспортировку единицы продукта ( C_i_,_j) между этими пунктами, т.е.

v_j – u_i= c_i_,_j. для x_i_,_j> 0

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

v_j – u_i< C_i_,_j. для x_i_,_j= 0

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

Такойметод применим лишь для условий так называемых «закрытых» задач, т.е. когда мощности поставщиков и потребителей сбалансированы. В случае несбалансированности мощностей поставщиков и потребностей потребителей задача приводится к «закрытой» при помощи добавления дополнительного поставщика или потребителя и переноса ему излишков или недостатков продукции [4].

2.3 «Числовая» модель задачи.

В рассматриваемой ситуации A_i(количество поставщиков зерна) равно 3, и B_j (количество потребителей - мелькомбинаты) равно 2. Кроме этого зерно поступает от поставщиков к потребителям через посредников (элеваторы), число которых равно 3. В таблице 1 предоставлены данные по суммарные затраты на транспортировку и обработку зерна (в расчете на 1 ц) на каждом из элеваторов. Суммарно из всех пунктов производства можно поставить 100 тыс.ц. зерна, а элеваторы могут переработать 110 тыс. ц, а суммарные потребности мелькомбинатов равны 100 тыс. ц [2].

Таблица 1.

ПотребителиПоставщики	Мощность элеваторов			Потребность мелькомбинатов
ПотребителиПоставщики	Михайловское	Лебедево	Озерное	Боровое	Мамонтово
Заря	14	14	15	35
Восход	16	11	9	45
Радуга	15	15	12	20
Михайлово	2	6	20
Лебедево	7	3	55
Озерное	4	9	25
20	55	25	40	60

3. Разработка динамических моделей для транспортно-производственной системы.

3.1 Однопродуктовая многоэтапная транспортно-производственная модель.

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

A_i(количество поставщиков зерна) равно 3, и B_j (количество потребителей - элеваторов) равно 3. В таблице 2 предоставлены данные по суммарные затраты на транспортировку и обработку зерна (в расчете на 1 ц) на каждом из элеваторов. Суммарно из всех пунктов производства можно поставить 100 тыс.ц. зерна [2].

Таблица 2

ПотребителиПоставщики	Михайловское	Лебедево	Озерное	Мощностьпоставщиков
Заря	14	14	15	35
Восход	16	11	9	45
Радуга	15	15	12	20
Резерв	0	0	0	10
Потребностипотребителей	20	55	25	110

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

Таблица 3.

ПотребителиПоставщики	Михайловское		Лебедево		Озерное		Мощностьпоставщиков
Заря	14	20	14	15	15	35
Восход	16	11	40	9	5	45
Радуга	15	15	12	20	20
Потребностипотребителей	20		55		25		110

Для первоначального плана (табл. 2) суммарные затраты на транспортировку и обработку зерна составляют 1215 у.е.

Нетрудно убедиться, что в нашем случае при использовании тех же направлений другой допустимый план построить нельзя. Изменение объема перевозок в любой из занятых клеток немедленно приведет к возникновению дисбаланса. Другой допустимый план можно построить, использовав лишь незанятые клетки таблицы. Таких допустимых планов можно построить очень много и каждый из них будет характеризоваться своим значением целей функции. Возникает вопрос о способе целенаправленного построения новых планов с улучшенной целевой функцией. Его решение основано на потенциалах и сформулированном выше признаке оптимальности.

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

v₁ - u₁ = 14	v₂ – u₁ = 14	v₂ - u₂ = 11
v₃ - u₂ = 9	v₃ - u₃ = 12	v₃ - u₄ = 0

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

Пусть u₁ = 0, тогда

v₁ = 14; v₂ = 14; u₂ = 3; v₃ =12; u₃ = 0; u₄ = 12.

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

∆_i,j = v_j - u_i - t_i,j

∆_1,3 = 12- 0 - 15 = -3

∆_2,1 = 14 – 3 – 16 = -5

∆ _3,1 = 14 – 0 – 15 = -1

∆_3,2 = 14- 0 - 15 = -1

∆_4,1 = 14 – 12 – 0 = +2

∆_4,2 = 14 – 12 – 0 = +2

Таблица 4

Потенциалы и направления улучшения опорного плана

ПотребителиПоставщики	Михайловское		Лебедево		Озерное		Мощностьпоставщиков
Заря	14	20	14	15	15	∆₁_,₃ = -3	35
Восход	16	∆ ₂_,₁ = -5	11	40	9	5	45
Радуга	15	∆₃_,₁ = -1	15	∆₃_,₂ = -1	12	15	20
Потребностипотребителей	20		55		25		110

Отрицательные величины ∆_i,j показывают, что везти по данному направлению невыгодно. Разница цен у потребителей и поставщиков не покрывает транспортных расходов и на каждой единице транспортируемого продукта мы будет терпеть убытки (по сравнению с предыдущим опорным планом) в размере ∆_i,j . В клетках, где ∆_i,j > 0, наоборот, может быть получен эффект в размере ∆_i,j на единицу перераспределяемого продукта. В рассматриваемом примере таких клеток две, причем обе имеют значение +2. Выберем любую из них, пусть это будет клетка на пересечении 4-ой строки и 2-го столбца и пометим ее плюсом. Определяя объем поставок в эту клетку, следует руководствоваться следующими соображениями:

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

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

Следовательно, вместо вошедшей клетки, одна, содержащаяся в предыдущем плане, должна быть исключена. Оба условия легко выполнить, если перераспределение поставок осуществлять по контуру (табл.4). Искомую величину перераспределяемой поставки определит минимальное значение, стоящее в клетках со знаком минус. В данном случае - 10 тыс. ц. Меньше этой величины перераспределять невыгодно, так как уменьшается эффект от улучшения плана и кроме того, на единицу превышается допустимое количество загружаемых клеток. Больше перераспределять нельзя, потому что в одной из клеток появится отрицательная перевозка, что абсурдно.