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

--PAGE_BREAK--Таким образом, для принятия оптимального решения любой экономической задачи необходимо построить ее экономико-математическую модель, по структуре включающую в себе систему ограничений, целевую функцию, критерий оптимальности и решение.
Для моделирования транспортно-производственных систем используется задачи линейного программирования, а именно транспортные задачи. Общая формулировка задачи имеет следующий вид: пусть осуществляется производство некоторого товара в пунктах A1, A2,…,Am. Объем производства товара в каждом пункте равен соответственно a1,a2,…,am. Товар необходимо доставить в магазины или потребителям, находящимся в других населенных пунктах: B1,B2,…,Bn. Известна потребность каждого потребителя в товаре: b1,b2,…,bn. Задана также стоимость Cij транспортировки товара из каждого пункта производства Ai каждому потребителю Bj. Требуется составить план завоза товара в магазины, обеспечивающий удовлетворение их спроса при минимальных транспортных издержках.
Методика построения экономико-математической модели состоит в том, чтобы экономическую сущность задачи представить математически, используя различные символы, переменные и постоянные величины, индексы и другие обозначения. Все условия задачи необходимо записать в виде уравнений или неравенств. Поэтому, в первую очередь необходимо определить систему переменных величин, которые могут для конкретной задачи обозначить искомый объем производства продукции на предприятии, количество перевозимого груза поставщиками конкретным потребителям [4].
2.2 Формальная постановка и математическая запись.
Оптимизационная задача – это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений.
Выше описаны условия задачи, которая может быть сведена к решению так называемой однопродуктовой многоэтапной транспортно-производственной модели. Рассматривается один продукт, который от пункта производства до конечного потребителя проходит несколько стадий транспортировки и переработки. Путем несложных преобразований, такую модель можно свести к классической транспортной задаче, методы решения которой описан ниже.
Формальная постановка и математическая запись задачи.
Дано:
Ai – множество наименований поставщиков;
Bj – множество наименований потребителей;
ai — объем произведенной продукции в i -ом пункте(I  N);
bj — платежеспособный спрос на продукцию в j-ом пункте (j  M);
Cij — затраты на транспортировку единицы продукции от i-го поставщика j-му потребителю.
Требуется найти такие объемы транспортировки продукции от каждого поставщика к каждому потребителю ( xi,j > 0, для i = N и j = M) ), при которых достигается минимум транспортных затрат (что при фиксированных ценах реализации продукции равносильно максимизации прибыли), то есть:
<shapetype id="_x0000_t75" coordsize=«21600,21600» o:spt=«75» o:divferrelative=«t» path=«m@4@5l@4@11@9@11@9@5xe» filled=«f» stroked=«f»><path o:extrusionok=«f» gradientshapeok=«t» o:connecttype=«rect»><lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_i1025" type="#_x0000_t75" o:ole=""><imagedata src=«50792.files/image001.wmz» o:><img width=«183» height=«51» src=«dopb236699.zip» v:shapes="_x0000_i1025">                    (1.1)
При этом должны соблюдаться условия:
— продукции должно быть вывезено не более произведенного количества:
<shape id="_x0000_i1026" type="#_x0000_t75" o:ole=""><imagedata src=«50792.files/image003.wmz» o:><img width=«96» height=«46» src=«dopb236700.zip» v:shapes="_x0000_i1026">, <shape id="_x0000_i1027" type="#_x0000_t75" o:ole=""><imagedata src=«50792.files/image005.wmz» o:><img width=«39» height=«19» src=«dopb236701.zip» v:shapes="_x0000_i1027">                         (1.2)
— платежеспособный спрос должен покрываться:
<shape id="_x0000_i1028" type="#_x0000_t75" o:ole=""><imagedata src=«50792.files/image007.wmz» o:><img width=«80» height=«36» src=«dopb236702.zip» v:shapes="_x0000_i1028">, <shape id="_x0000_i1029" type="#_x0000_t75" o:ole=""><imagedata src=«50792.files/image009.wmz» o:><img width=«45» height=«21» src=«dopb236703.zip» v:shapes="_x0000_i1029">                          (1.3)     
Рассмотрим один из методов решения транспортной задачи – метод потенциалов, основанный на идее последовательного улучшения допустимого решения. В методе потенциалов, как и во многих других методах оптимизации, используется следующий прием: строится система оценок (цен-измерителей), позволяющая определить, является ли построенный план оптимальным (другими словами, построить признак оптимальности). Применительно к транспортной задаче признак оптимальности формулируется следующим образом: допустимый план перевозок тогда и только тогда является оптимальным, когда каждому пункту производства и потребления можно поставить в соответствие оценки (потенциалы), удовлетворяющие двум условиям:
Во-первых, разность оценок пунктов потребления ( vj) и производства ( ui), между которым запланированы перевозки, равна затратам на транспортировку единицы продукта ( Ci,j) между этими пунктами, т.е.
vj – ui= ci,j. для xi,j> 0
Во-вторых, аналогичные разности для всех остальных направлений (не вошедших в план) не превосходят затрат на транспортировку.
vj – ui< Ci,j. для xi,j= 0
По сути дела признак оптимальности представляет собой математическое выражение здравого смысла — если какая-то перевозка осуществляется, то цена в пункте потребления равна цене в пункте производства плюс транспортные затраты или (что одно и то же) разница цен на оптимальном направлении равна транспортным затратам. В случае выбора менее эффективного маршрута разница цен не покрывает транспортных затрат и получается убыток. С помощью сформулированного признака оптимальности можно не только проверить на оптимальность любой допустимый план, но, и в случае неоптимальности, указать способ улучшения этого плана. Покажем это на примере решения задачи, изложенной в данной ситуации, предварительно сделав два важных замечания.
Такой метод применим лишь для условий так называемых «закрытых» задач, т.е. когда мощности поставщиков и потребителей сбалансированы. В случае несбалансированности мощностей поставщиков и потребностей потребителей задача приводится к «закрытой» при помощи добавления дополнительного поставщика или потребителя и переноса ему излишков или недостатков продукции [4].
2.3 «Числовая» модель задачи.
В рассматриваемой ситуации Ai(количество поставщиков зерна) равно 3, и Bj (количество потребителей — мелькомбинаты) равно 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 Однопродуктовая многоэтапная транспортно-производственная модель.
Возьмем из задачи, описанной выше, только половину условия:
Ai(количество поставщиков зерна) равно 3, и Bj (количество потребителей — элеваторов) равно 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 у.е.
Нетрудно убедиться, что в нашем случае при использовании тех же направлений другой допустимый план построить нельзя. Изменение объема перевозок в любой из занятых клеток немедленно приведет к возникновению дисбаланса. Другой допустимый план можно построить, использовав лишь незанятые клетки таблицы. Таких допустимых планов можно построить очень много и каждый из них будет характеризоваться своим значением целей функции. Возникает вопрос о способе целенаправленного построения новых планов с улучшенной целевой функцией. Его решение основано на потенциалах и сформулированном выше признаке оптимальности.
Используя принятые обозначения, запишем следующие соотношения между оценками для клеток, вошедших в план:
v1 — u1 = 14
v2 – u1 = 14
v2 — u2 = 11
v3 — u2 = 9
v3 — u3 = 12
v3 — u4 = 0
Число неизвестных в данной системе уравнений на единицу больше числа уравнений, поэтому решение может быть получено лишь с точностью до постоянного слагаемого. Приравняв значение одной из переменных какому-либо числу, однозначно находим значения других переменных.
Пусть u1 = 0, тогда
v1 = 14; v2 = 14; u2 = 3; v3 =12; u3 = 0; u4 = 12.
Используя найденные потенциалы, рассчитаем для всех незанятых клеток величины: и поставим их (с соответствующим знаком) в табл. 4

∆i,j = vj — ui — ti,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
∆1,3 = -3
35
Восход
16
∆ 2,1 = -5
11
40
9
5
45
Радуга
15
∆3,1 = -1
15
∆3,2 = -1
12
15
20
Потребности
потребителей
20
55
25
110
Отрицательные величины ∆i,j показывают, что везти по данному направлению невыгодно. Разница цен у потребителей и поставщиков не покрывает транспортных расходов и на каждой единице транспортируемого продукта мы будет терпеть убытки (по сравнению с предыдущим опорным планом) в размере ∆i,j. В клетках, где ∆i,j > 0, наоборот, может быть получен эффект в размере ∆i,j на единицу перераспределяемого продукта. В рассматриваемом примере таких клеток две, причем обе имеют значение +2. Выберем любую из них, пусть это будет клетка на пересечении 4-ой строки и 2-го столбца и пометим ее плюсом. Определяя объем поставок в эту клетку, следует руководствоваться следующими соображениями:
во-первых, поставив в нее какой-то объем перевозок, мы должны вычесть эту же величину из других занятых клеток, чтобы не нарушить балансовых соотношений по ввозу и вывозу.
во-вторых, число клеток, включенных в новый план должно оставаться неизменным на единицу меньше суммарной численности поставщиков и потребителей.
Следовательно, вместо вошедшей клетки, одна, содержащаяся в предыдущем плане, должна быть исключена. Оба условия легко выполнить, если перераспределение поставок осуществлять по контуру (табл.4). Искомую величину перераспределяемой поставки определит минимальное значение, стоящее в клетках со знаком минус. В данном случае — 10 тыс. ц. Меньше этой величины перераспределять невыгодно, так как уменьшается эффект от улучшения плана и кроме того, на единицу превышается допустимое количество загружаемых клеток. Больше перераспределять нельзя, потому что в одной из клеток появится отрицательная перевозка, что абсурдно.
Новый (оптимальный) план и соответствующая ему система оценок приведен в табл.5
Таблица 5
Потребители
Поставщики
Михайловское
Лебедево
Озерное
Мощность
поставщиков
u
Заря
14
20
14
15
15
∆1,3 = -3
35
0
Восход
16
∆ 2,1 = -2
11
30
9
15
45
3
Радуга
15
∆3,1 = -1
15
∆3,2 = -1
12
20
20
0
Потребности
потребителей
20
55
25
110
v
14
14
12
Рассчитав значения потенциалов vj и ui и величины ∆i,j запишем их соответствующие клетки (табл.5). Значения ∆i,j во всех незанятых клетках не больше нуля, что свидетельствует об оптимальности построенного плана, для которого значение целевой функции равно 1195. По сравнению с первым опорным планом затраты удалось снизить на 20 единиц… Заметим, в одной из клеток ∆4,1 = 0, что свидетельствует о неоднозначности оптимального плана, т.е. достигнутое значение целевой функции может быть получено и при других значениях переменных. При решении данной задачи в программе Excel мы получим значения, которые приведены в таблице 5 [5].
3.2 Двойственная задача.
Предположим, что речь идет об установлении таких цен, которые бы стимулировали организацию, ответственную за выполнение перевозок, действовать в соответствии с оптимальным планом и затрачивать минимум средств на перевозку. Разность цен на продукт у потребителей и поставщиков должна быть такой, чтобы исключить возможность «спекуляции», т.е. по каждому направлению транспортировки она не должна превышать транспортных расходов.
<shape id="_x0000_i1030" type="#_x0000_t75" o:ole=""><imagedata src=«50792.files/image011.wmz» o:><img width=«120» height=«36» src=«dopb236704.zip» v:shapes="_x0000_i1030">, i =1…N, j=1…M        (1.4)
Критерием оптимальности в такой задаче можно принять разность взвешенной по оценкам продукции в пунктах потребления и пунктах поставок, которую нужно максимизировать:
<shape id="_x0000_i1031" type="#_x0000_t75" o:ole=""><imagedata src=«50792.files/image013.wmz» o:><img width=«251» height=«55» src=«dopb236705.zip» v:shapes="_x0000_i1031">         (1.5)
Задача, модель которой описывает соотношения (1.4) и (1.5), называется двойственной к задаче (1.1) и (1.3).
Отметим, что решение задачи (1.4) и (1.5) неразрывно связано с оптимальным решением прямой задачи (1.1) - (1.3). Именно для оптимальных значений переменных xi,j > 0 соотношения (1.5) выполняются как строгие равенства.
Важным для анализа свойством двойственных задач является совпадение оптимальных значений целевых функций (1.1) и (1.5):
<shape id="_x0000_i1032" type="#_x0000_t75" o:ole=""><imagedata src=«50792.files/image015.wmz» o:><img width=«288» height=«50» src=«dopb236706.zip» v:shapes="_x0000_i1032">          (1.6)
В справедливости соотношения (1.6) легко убедиться на нашем примере, подставив в него конкретные значения из табл.1.3.
Поскольку в оптимальном случае целевые функции прямой и двойственной задач совпадают, то наличие в правой части равенства оценок дает возможность ранжирования поставщиков и потребителей по степени эффективности. Так, величина оценки ui характеризует изменения целевой функции при изменении мощности поставщика на единицу. Легко заметить, что чем выше соответствующая оценка поставщика, тем выгоднее наращивать в нем производство.
Рассуждения о сравнительной эффективности потребителей прямо противоположны. Так как оценка пункта потребления vj показывает прирост производственно-транспортных затрат в расчете на единицу прироста потребности в этом пункте, то самым эффективным будет пункт потребления, имеющий минимальное значение оценки (в рассмотренном выше случае — элеватор в Озерном). Следует иметь в виду, что пользоваться оценками и делать на их основе какие-либо выводы можно лишь в пределах устойчивости оптимального плана, т.е. до тех пор, пока не меняется базис решения. Если же стоит задача проанализировать рассмотренную ситуацию при резком (значительном) изменении исходных данных, то это следует делать путем проведения вариантных расчетов, введя в условия задачи необходимые изменения и заново ее оптимизировав. При наличии стандартного программного обеспечения и средств диалогового общения с ПЭВМ такие расчеты не представляют затруднений [5].
    продолжение
--PAGE_BREAK--