Оптимизация транспортировки продукции

Венгерский  метод наиболее эффективен при решении  транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины ОО/2 (ОО суммарная  невязка подготовительного этапа).

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

Методы определения  первоначального опорного плана. Метод  аппроксимации Фогеля.

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

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

Метод минимального элемента.

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

меньшее из чисел. Затем из рассмотрения исключают либо строку,

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

Усложнённые задачи транспортного типа

Ряд экономических  задач легко сводимы к транспортной задаче. Рассмотрим наиболее часто  встречающиеся ситуации в экономике предприятия.

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

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

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

3.   ряд   транспортных   маршрутов,   по   которым   необходимо   доставить грузы, имеют ограничения  по пропускной способности. Если, например, по маршруту А;В| Можно  провести не более ц единиц  груза, то В, - и столбец матрицы  разбивается на два столбца В,',  и В". .В первом столбце спрос принимается   равным   разности   между   действительным   спросом,    и

ограничением  во втором - равным ограничению.

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

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

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

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

7.         необходимо в одно время распределить  груз различного рода по

потребителям.

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

 

 

2. Построение оптимизационной транспортной модели.

 

Вариант 6. Совхоз обладает тракторами следующих марок: К-700 – 4 шт., Т-75 – 2 шт., МТЗ – 5 шт., ДТ-28 – 26 шт. В период весеннее полевых работ эти тракторы могут выработать такие объемы работ (в га у. п.): К-700 – 500, Т-75 – 260, МТЗ – 380, ДТ-28 – 360. За период надо провести следующие работы: пахота – 400, боронование – 300, посев зерновых – 250, посев пропашных культур – 550 га у. п. Себестоимость проведения тракторных работ в расчете на 1 га у. п. задана (табл. 6). Требуется составить такой план распределения тракторов по видам работ, который обеспечивает минимальную себестоимость их проведения.

Таблица 6

Стоимость проведения тракторных работ, р.

Вид работ	Марка трактора
	К-700	Т-75	МТЗ	ДТ-28
Пахота	4,0	3,4	4,7	6,3
Боронование	4,5	3,9	4,2	5,7
Посев зерновых	4,9	5,2	4,9	3,7
Посев пропашных	5,0	5,1	6,5	4,9

 

 

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

Таблица 6

 

Показатели	Корма, ц			Требуется в сутки не менее
	концентр.	грубые	силосные
Содержание корм. ед., кг	110,0	40,0	20,0	12,0
Содержание протеина, кг	10,0	3,0	2,0	2,0
Себестоимость, р.	8,0	2,5	1,5

Примечание. Концентрированных кормов в рационе  должно быть не менее 5 кг.

 

Вариант 6

 

 

 

3 Анализ решения

 

Для решения применяем команду  Поиск решения —» Сервис. Для   анализа   результатов   полученного   решения   запишем   значение переменных.

Задача 1.
Число тракторов	Марка трактора
Вид работ	К-700	Т-75	МТЗ	ДТ-28
Пахота	1	0	0	0
Боронование	0	0	1	0
Посев зерновых	0	0	0	1
Посев пропашных	0	1	0	1
Итого	1	1	1	2
Лимит	4	2	5	26
Объем работ на ед.	500	260	380	360
Себестоимость	Марка трактора
Вид работ	К-700	Т-75	МТЗ	ДТ-28
Пахота	4	3,4	4,7	6,3
Боронование	4,5	3,9	4,2	5,7
Посев зерновых	4,9	5,2	4,9	3,7
Посев пропашных	5	5,1	6,5	4,9

 

Суммарные затраты	Марка трактора
Вид работ	К-700	Т-75	МТЗ	ДТ-28
Пахота	2000	0	0	0
Боронование	0	0	1596	0		Общая себестоимость
Посев зерновых	0	0	0	1332		8018
Посев пропашных	0	1326	0	1764
Объем работ	Марка трактора
Вид работ	К-700	Т-75	МТЗ	ДТ-28	итого	лимит
Пахота	500	0	0	0	500	400
Боронование	0	0	380	0	380	300
Посев зерновых	0	0	0	360	360	250
Посев пропашных	0	260	0	360	620	550
Задача целочисленная - трактора распредляются  по видам работ целиком,
в целочисленных задачах "Поиск  решения" выводит только отчет  по результатам.
Трактор К-700 в одном количестве занимается пахотой, трактор Т-75 в одном количестве
занимается посевом пропашных, трактор  МТЗ в одном количестве занимается
боронованием, трактор ДТ-28 один занимается посевом зерновых и один трактор  ДТ-28
занимается посевом пропашных.
Суммарная минимальная себестоимость 8018 руб.     Задача 2.                               Корма концентр. грубые силосные         Кол-во 5 0 0   общая себестоимость Себестоимость 8 2,5 1,5   40                     Ограничения Коэффициенты Левая часть Правая часть     сод-ие корм. ед. 110 40 20 550 12     сод-ие протеина 10 3 2 50 2                     Итак, оптимальный рацион кормления  коров составляет 5 кг концентрированных  кормов остальных кормов для кормления не требуется.         при этом общая себестоимость составляет 40 руб.                          Задача 3                 F = 8x1 - 3x2 + x3 + 6x4 - 5x5 → max           2x1 + 4x2 + x3 + x4 - 2x5 =28           x1 - 2x2 + x4 + x5 = 31           -x1 + 3x2 + 5x3 + 4x4 - 8x5 = 118       x1, x2, x3, x4, x5 ≥ 0                         Переменная x1 x2 x3 x4 x5     значение 0 0 6 28 3   F = коэффициент 8 -3 1 6 -5   159                 Ограничения Коэффициент Левая часть Правая часть 1) 2 4 1 1 -2 28 28 2) 1 -2 0 1 1 31 31 3) -1 3 5 4 -8 118 118                 Итак, полученный оптимальный план:           х* = (0; 0; 6; 28; 3)           Максимум функции F(max) = 159.