Схема оформления и методы решения задач транспортного типа

Ограничения по строкам исходной матрицы:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅=149,

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅=163,

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅=382;

Ограничения по столбцам исходной матрицы:

x₁₁+x₂₁+x₃₁=139,

x₁₂+x₂₂+x₃₂=165,

x₁₃+x₂₃+x₃₃=120,

x₁₄+x₂₄+x₃₄=130,

x₁₅+x₂₅+x₃₅=140.

3) балансовое условие:

149+163+382 = 139+165+120+130+140=694;

4) условие неотрицательности неизвестных:

x₁₁ 0, x₁₂ 0, x₁₃ 0, x₁₄ 0, x₁₅ 0, x₂₁ 0, x₂₂ 0, x₂₃ 0, x₂₄ 0, x₂₅ 0, x₃₁ 0,x₃₂ 0, x₃₃ 0, x₃₄ 0, x₃₅ 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

Табличная форма записи исходных данных задачи

Порядок выполнения задачи:

1) ^{*) -} + 100N; ^**) - + N (N - номер студента в группе)

2) Записать математическое условие задачи в структурном виде.

3) Найти опорное решение методом аппроксимации. Опорное решение проверить методом потенциалов, получить оптимальное решение.

Задачу решить с дополнительными ограничениями:

вариант 1: не менее половины площади посева однолетних трав на сено должно быть размещено на 3-м участке;

вариант 2: посевы однолетних трав на з/к на четвертом участке должны составлять точно 300 га;

вариант 3: весь картофель разместить на четвертом участке;

вариант 4: посевы кукурузы на втором участке должны занимать не более 900.

4) Записать ответ задачи.