Экономические модели сводящиеся к транспортной модели

      В каждом столбце табл. 1.2.2 находим минимальные тарифы и обводим их кружками. Заполняем клетки, в которых стоят указанные числа. Для этого в каждую из клеток записываем максимально допустимое число. Например, в клетку, находящуюся на пересечении строки А₁ и столбца В₃, записываем число 120. В эту клетку нельзя поместить большее число, поскольку в таком случае были бы превышены потребности пункта назначения В₃.

      В результате заполнения отмеченных выше клеток получен так называемый условно оптимальный план, согласно которому полностью удовлетворяются потребности пунктов назначения В₁, В₂, В₃ и В₄ и частично – пункта назначения В₅. При этом полностью распределены запасы пункта отправления А₂, частично – пункта отправления А₁ и остались совсем нераспределенными запасы пункта отправления А₃.

      После получения условно оптимального плана определяем избыточные и недостаточные  строки. Здесь недостаточной является строка А₂, так как запасы пункта отправления А₂ полностью использованы, а потребности пункта назначения В5 удовлетворены частично. Величина недостатка равна 80 ед.

      Строки  А₁ и А₃ являются избыточными, поскольку запасы пунктов отправления А₁ и А₃ распределены не полностью. При этом величина избытка строки А₁ равна 60 ед., а строки А₃ – 20 ед. общая величина избытка 60+20=80 совпадает с общей величиной недостатка, равной 80.

      После определения избыточных и недостаточных  строк по каждому из столбцов находим  разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных  клетках. В данном случае эти разности соответственно равны 5,4,2,1 (табл. 1.2.2).  Для столбца В₃ разность не определена, так как число, записанное в кружке в данном столбце, находится в положительной строке. В столбце В₁ число, стоящее в кружке, равно 1, а в избыточных строках в клетках данного столбца наименьшим является число 6. Следовательно, разность для данного столбца равна 6-1=5. Аналогично находим разности для других столбцов: для В₂ 12-8=4; для В₄ 7-5=2; для В₅ 4-3=1.

      Выбираем  наименьшую из найденных разностей, которая является промежуточной рентой. В данном случае промежуточная рента равна 1 и находится в столбце В₅. Найдя промежуточную ренту, переходим к табл. 1.2.3

Табица 1.2.3 Промежуточная рента

     

Пункты  отправления	Пункты  назначения					Запасы	Недостаток(-), Избыток(+)
	В1	В2	В3	В4	В5
А1	7	12	4 120	8	5	180	+60
А2	2 110	9 90	7	6 80	4 70	350	-60
А3	6	13	8	7	4 20	20	-0
Потребности	110	90	120	80	150	550
Разности	5	3	–	2	1

      В данной таблице в строках А₁ и А₃ (являющихся избыточными) переписываем соответствующие тарифы из строк А₁ и А₃ табл. 1.2.2. элементы строки А₂ (которая была недостаточной) получаются в результате прибавления к соответствующим тарифам, находящимся  в строке А₂ табл. 1.2.2, промежуточной ренты, т.е. 1.

      В таблице 1.2.3 число заполняемых клеток возросло на одну. Это обусловлено тем, что число минимальных тарифов, стоящих в каждом из столбцов данной таблицы, возросло на единицу, а именно в столбце В₅ теперь имеются два минимальных элемента 4. Эти числа заключаем в кружки; клетки, в которых они стоят, следует запомнить. Необходимо заполнить и клетки, в которых в которых стоят наименьшие для других столбцов тарифы. Это клетки табл. 1.2.3, в которых соответствующие тарифы заключены в кружки. После того как указанные клетки определены, устанавливаем последовательность их заполнения. Для этого находим столбцы (строки), в которых имеется лишь одна клетка для заполнения. Определив и заполнив некоторую клетку, исключаем из рассмотрения соответствующий столбец (строку) и переходим к заполнению следующей клетки. В данном случае заполнение клеток проводим в такой последовательности. Сначала заполняем клетки А₁В₃, А₂В₁, А₂В₂, А₂В₄, так как они являются единственными клетками для заполнения в столбцах В₁, В₂, В₃ и В₄. После заполнения указанных клеток заполняем клетку А₃В₅, поскольку она является единственной для заполнения в строке А3. Заполнив эту клетку, исключаем из рассмотрения строку А₃. Тогда в столбце В₅ останется все лишь одна клетка для заполнения. Это клетка А₂В₅, которую заполняем. После заполнения клеток устанавливаем избыточные и недостаточные строки. Как видно из табл. 1.2.3, еще имеется нераспределенный остаток. Следовательно получен условно оптимальный план задачи и нужно перейти к новой таблице. Для этого по каждому их столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках. Среди этих разностей наименьшая равна 1. Это и есть промежуточная рента. Переходим к следующей таблице (табл. 1.2.4).

 

 

     Таблица 1.2.4 Оптимальный план транспортной задачи

     

Пункты  отправления	Пункты  назначения					Запасы	Недостаток(-), Избыток(+)
	В1	В2	В3	В4	В5
А1	7	12	4 120	8	5 60	180	0
А2	3 110	10 90	8	7 80	5 70	350	0
А3	7	14	9	8	5 20	20	0
Потребности	110	90	120	80	150	550

      В новой таблице элементы строк  А₂ и А₃ получены в результате прибавления к соответствующим числам строк  А₂ и А₃(являющихся недостаточными) табл. 1.2.3 промежуточной ренты, т. е 1. В результате в табл. 1.2.4 число клеток ля заполнения возросло еще на одну и стало равным 6. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А₁В₃, А₂В₁, А₂В₂, А₂В₄, а затем А₃В₅, А₂В₅, А₁В₅. В результате все имеющиеся запасы поставщиков распределяются в соответствии с фактическими потребностями пунктов назначения. Число заполненных клеток равно 7, и вес они имеют наименьший показатель C_ij. Следовательно получен оптимальный план исходной транспортной задачи:

X=

      При этом плане перевозок общие затраты  таковы:

      S=4*120+5*60+1*110+8*90+5*80+3*70+4*20=2300.

 

     

2 Практическая часть

      Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами C_ij (i, j = 1,2,…, n). Требуется найти назначение кандидатов на все работы, дающие минимальные суммарные затраты, при этом каждого кандидата можно назначать только на одну работу и каждая работа может быть занята только одним кандидатом. Исходные данные приведены в таблице:

     Таблица .2.4 Исходные данные

     

Ai Bj	B1	B2	B3	B4
A1	3	7	3	8
A2	2	4	4	5
A3	4	7	2	8
A4	9	7	3	8

     Входные данные:

     n – количество кандидатов и работ, целый тип данных

     C (n, n) - затраты (руб.), вещественный тип данных.

     Выходные  данные:

     Smin- суммарные затраты (руб.), вещественный тип данных;

     X (n, n) - назначение кандидата на работу, целый тип данных.

 
 
      2.1 Решение задачи с помощью математического аппарата

     Определим опорный план транспортной задачи методом минимальной стоимости, учитывая что каждого кандидата можно назначать только на одну работу и каждая работа может быть занята только одним кандидатом.

Таблица 2.1.1 Опорный план методом минимальной стоимости

     

Ai                       Bj	B1	B2	B3	B4
A1	3 0	7 1	3 0	8 –
A2	2 1	4 –	4 –	5 –
A3	4 –	7 –	2 1	8 –
A4	9 –	7 –	3 0	8 1

     Минимальные суммарные затраты составят:

     F=0*3+1*7+0*3+1*2+1*2+0*3+1*8=19

     Для нахождения оптимального плана используем метод потенциалов.

     Составим  систему уравнений U_i+V_j =C_ij для заполненных клеток транспортной таблицы и определим значения U_i и V_j.

     U₁+V₁=3  U₁=0  V₁=3

     U₁+V₂=7  U₂=-1  V₂=7

     U₁+V₃=3  U₃=0  V₃=3

     U₂+V₁=2  U₄=0  V₄=8

     U₃+V₃=3

     U₄+V₃=3

     U₄+V₄=8

     Рассчитаем  величины ∆_ij= U_i+V_j-C_ij для свободных клеток таблицы.

     ∆₁₄=U₁+V₄-C₁₄=0+8-8=0

     ∆₂₂=U₂+V₂-C₂₂=-1+7-4=2

     ∆₂₃=U₂+V₃-C₂₃=-1+3-4=-2

     ∆₂₄=U₂+V₄-C₂₄=-1+8-5=2

     ∆₃₁=U₃+V₁-C₃₁=0+3-4=-1

     ∆₃₂=U₃+V₂-C₃₂=0+7-7=0

     ∆₃₄=U₃+V₄-C₃₄=0+8-8=0

     ∆₄₁=U₄+V₁-C₄₁=0+3-9=-6

     ∆₄₂=U₄+V₂-C₄₂=0+7-7=0

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

(1,1) 0 1(1,2) 1

                 min {1, 1}=1 

(2,1)                       (2,2)

      1 0     1

 

Таблица 2.1.3 Опорный план методом потенциалов

     

Ai                       Bj	B1	B2	B3	B4
A1	3 1	7 –	3 0	8 –
A2	2 0	4 1	4 –	5 –
A3	4 –	7 –	2 1	8 –
A4	9 –	7 –	3 0	8 1