Схема оформления и методы решения задач транспортного типа
Демонстрационная задача №1
Найти минимум затрат на перевозку кормов с севооборотных массивов на животноводческие фермы. Данные по затратам на перевозку единицы груза с учетом удаленности участков от производственных центров приведены в табл. 1.
Таблица 1
Табличная форма записи исходных данных транспортной задачи
 Фермы
| Удельные затраты на перевозку груза, руб/т | Ресурсы | ||||
| Севообороты | Ферма 1 | Ферма 2 | Ферма 3 | Ферма 4 | Ферма 5 | севооборотов, т |
| Полевой-1 | ||||||
| Полевой-2 | ||||||
| Кормовой | ||||||
| Потребности ферм в кормах, т |
Порядок выполнения задачи:
1. Записать математическую формулировку задачи в общем виде.
2. Дать развернутую запись условия задачи с числовым значением переменных и ресурсов.
3. Задачу решить, используя метод наилучшего элемента.
4. Записать ответ.
Определение опорного решения задачи методом минимального элемента
Формализация исходных данных задачи:
Введем следующие обозначения:
m - количество севооборотов (пунктов отправления);
n - количество ферм (пунктов назначения);
i - номер севооборота: 
j - номер фермы: 
i- i, m – индексы строк; j, n – индексы столбцов;
стоимость перевозки единицы объема продукции с i –го севооборота на j-ую ферму;
- 
объем перевозимой продукции с i –го севооборота на j –ую ферму;
- объем продукции, производимой на i –ом севообороте и предназначенной для транспортировки на фермы, т;
-потребность j –ой фермы в кормах, т;
- целевая функция.
Исходная информация обычно заносится в матрицу специального вида (табл.2)
Таблица 2
Табличная форма записи исходных данных
транспортной задачи
| Номера | Номера пунктов приема | Объемы производства | ||||
| севооборотов | … | n | продукции | |||
| C11 X11 | C12 X12 | C13 X13 | … | C1n X1n | A1 | |
| C12 X21 | C22 X22 | C23 X23 | … | C2n X2n | A2 | |
| … | … | … | … | … | … | … |
| m | Cm1 Xm1 | Cm2 Xm2 | Cm3 Xm3 | … | Cmn Xmn | AM |
 Максимальные объемы переработки продукции
| B1 | B2 | B3 | … | Bn | 
|
Сумма объемов продукции, производимой на всех севооборотных массивах, должна быть равна общей потребности ферм в кормах: найти такие объемы 
транспортировки кормов с севооборотных массивов на фермы, при которых целевая функция примет минимальное значение:
Запись задачи транспортного типа в структурной форме:
Ограничения по строкам:
Сумма перевозимых кормов с i –го севооборотного массива на j –е фермы должна быть равна запасу кормов данного севооборота:
Ограничения по столбцам:
Сумма объемов продукции, доставляемых на j –ую ферму со всех севооборотов, должна быть равна потребности в кормах на данной ферме:
Балансовое условие:
Сумма объемов продукции, производимой на всех севооборотных массивах, должна быть равна общей потребности ферм в кормах.
Условие не отрицательности переменных:
Проверка сбалансированности задачи
Должно быть 
149 + 163 + 382 = 694
139 +165 + 120 + 130 + 140 =694
Задача сбалансирована (закрыта).
Матричная запись исходных данных задачи после учета требований сбалансированности представлена в табл.3.
Таблица 3
Табличное представление исходных данных задачи
 Фермы
| Удельные затраты на перевозку груза, тыс.руб/т | Ресурсы | ||||
| Севообороты | Ферма 1 | Ферма 2 | ферма 3 | Ферма 4 | Ферма 5 | севооборотов, т |
| Полевой-1 | X11 | X12 | X13 | X14 | X15 | |
| Полевой-2 | X21 | X22 | X23 | X24 | X25 | |
| Кормовой | X31 | X32 | X33 | X34 | X35 | |
 Потребности ферм в кормах, т
|
1) целевая функция
Z=55x11+48x12+49x13+60x14+25x15+45x21+35x22+96x23+55x24+66x25+47x31+66x32+
+90x33+65x34+20x35 
min;
2) граничные условия
Ограничения по строкам исходной матрицы:
x11+x12+x13+x14+x15=149,
x21+x22+x23+x24+x25=163,
x31+x32+x33+x34+x35=382;
Ограничения по столбцам исходной матрицы:
x11+x21+x31=139,
x12+x22+x32=165,
x13+x23+x33=120,
x14+x24+x34=130,
x15+x25+x35=140.
3) балансовое условие:
149+163+382 = 139+165+120+130+140=694;
4) условие неотрицательности неизвестных:
x11 
0, x12 0, x13 0, x14 0, x15 0, x21 0, x22 0, x23 0, x24 0, x25 0, x31 0,x32 0, x33 0, x34 0, x35 0;
Получение опорного решения методом минимального элемента удобно проводить в таблице специального вида (табл.4).
Таблица 4
Получение опорного решения методом наилучшего минимального элемента
| Севообороты | Удельные затраты на перевозку груза, тыс.руб/т | Ресурсы | ||||
| Ферма 1 | Ферма 2 | Ферма 3 | Ферма 4 | Ферма 5 | севооборотов, т | |
  Полевой-1
| 149 147 | |||||
 Полевой-2
| ||||||
  Кормовой
| 382 242 | |||||
   Потребности ферм в кормах, т
|
Проверка опорного решения на выполнение граничных условий:
а) по строкам:
2+120+27=149
163=163
139+103+140=382
б) по столбцам:
139=139
163+2=165
120=120
27+103=140
Граничные условия по строкам и столбцам выполняются.
Проверка по числу занятых клеток 
:
Количество занятых клеток в опорном плане должно быть равно условию вырожденности:
, где m – число строк, n – число столбцов.
В нашем случае 
7 и (m+n-1)=3+5-1=7; то есть решение верное и невырожденное.
Вычисление целевой функции:
Z= 
=2*48+120*49+27*60+163*35+139*47+103*65
+140*20=29329
Проверка опорного решения на оптимальность.
Введем новые характеристики (потенциалы поставщиков и потребителей продукции 
и 
соответственно.
Вычисление потенциалов 
и 
:
Для занятых клеток 
За первый потенциал примем 
сonst – произвольное число; 
max=90, чтобы обеспечить положительность, тогда 
90+48=138 и т.д.
Оценка свободной клетки вычисляется по формуле 
При решении задач на min решение является оптимальным, если для всех свободных клеток 
. Для свободных клеток считаем оценки 
и размещаем их в правом нижнем углу свободной клетки (табл.5).
Таблица 5
Потенциалы 
и оценки для опорного решения задачи
| Севообороты | Удельные затраты на перевозку груза, тыс.руб/т | Ресурсы | ||||
 
| ||||||
| Ферма 1 | Ферма 2 | Ферма 3 | Ферма 4 | Ферма 5 | севооборотов, т |
  90 Полевой-1
| ||||||
    103 Полевой-2
| ||||||
 85 Кормовой
| ||||||
 Потребности ферм в кормах, т
|
В данном случае для всех свободных клеток условие оптимальности выполняется, поэтому полученное решение оптимально.
Целевую функцию вычисляем для контроля формул, используя вычисленные потенциалы и :
Z = 
Zконтр. = (62*139+68*165+69*120+80*130+35*140) – (20*149+33*163+15*382) =29329.
Формализованное представление оптимального решения задачи приведено в табл.6.
Таблица 6
Оптимальное решение задачи
 j
i
| Ресурсы, т | |||||
 Потребности,
т
|
Ответ: затраты на перевозку кормов с севооборотных массивов на животноводческие фермы будут минимальны и равны 29329 тыс. рублей при следующем распределении перевозок с севооборотов на фермы:
с полевого севооборота 1: 2 т на 2 ферму, 120 т на 3 ферму, 27т на 4 ферму;
с полевого севооборота 2: 163 т на 2 ферму;
с кормового севооборота: 139 т на 1 ферму, 103 т на 4 ферму, 140 т на 5 ферму.
Демонстрационная задача №2
Распределить посевы кормовых культур по 4 участкам земли различного плодородия таким образом, чтобы сбор кормов (в кормовых единицах) был максимальным. Исходные данные приведены в табл 7.
Таблица 7
Табличная форма записи исходных данных задачи
| № | Культуры | Урожайности культур по участкам (ц.к.е./га) | Площадь | |||
| п/п | I | II | III | IV | посева, га | |
| Кукуруза на силос | ||||||
| Одн.травы на з/к | 2300*) | |||||
| Одн. Травы на сено | 29**) | |||||
| Картофель | ||||||
| Горох | 18**) | |||||
| Мн.травы на сено | ||||||
| Площади участков, га | 2100*) |
Порядок выполнения задачи:
1) *) - + 100N; **) - + N (N - номер студента в группе)
2) Записать математическое условие задачи в структурном виде.
3) Найти опорное решение методом аппроксимации. Опорное решение проверить методом потенциалов, получить оптимальное решение.
Задачу решить с дополнительными ограничениями:
вариант 1: не менее половины площади посева однолетних трав на сено должно быть размещено на 3-м участке;
вариант 2: посевы однолетних трав на з/к на четвертом участке должны составлять точно 300 га;
вариант 3: весь картофель разместить на четвертом участке;
вариант 4: посевы кукурузы на втором участке должны занимать не более 900.
4) Записать ответ задачи.