Курсовая работа: Разработка динамических моделей для транспортно-производственной системы
Если экономико-математическая модель задачи линейна, то оптимальный план достигается в крайней точке области изменения переменных величин системы ограничений.
Таким образом, для принятия оптимального решения любой экономической задачи необходимо построить ее экономико-математическую модель, по структуре включающую в себе систему ограничений, целевую функцию, критерий оптимальности и решение.
Для моделирования транспортно-производственных систем используется задачи линейного программирования, а именно транспортные задачи. Общая формулировка задачи имеет следующий вид: пусть осуществляется производство некоторого товара в пунктах 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) ), при которых достигается минимум транспортных затрат (что при фиксированных ценах реализации продукции равносильно максимизации прибыли), то есть:
(1.1)
При этом должны соблюдаться условия:
- продукции должно быть вывезено не более произведенного количества:
, (1.2)
- платежеспособный спрос должен покрываться:
, (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-го столбца и пометим ее плюсом. Определяя объем поставок в эту клетку, следует руководствоваться следующими соображениями: