Классы экономико-математических моделей и методы их прикладного значения в экономике и управлении

       Рассмотрим задачу: имеется m различных работ и n кандидатов для их выполнения. Затраты на выполнение i-м кандидатом j-й работы, равняется с_ij. Каждый кандидат может выполнять только одну работу, а каждая работа может быть выполнена только одни кандидатом. Требуется распределить кандидатов по работам таким образом, чтобы минимизировать суммарные затраты на их выполнение.

     Математическая  постановка задачи имеет следующий  вид (формула 1.12).

     

,    (1.12)

     где f ( ) – целевая функция;

     с_ij – транспортные расходы;

     x_ij – совокупность переменных.

     Для решения задачи о назначениях  составляем таблицу 1.2.

     Таблица. 1.2 - Общий вид матрицы назначений

 

     Первый  столбец – номера кандидатов; первая строка – номера работ.

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

     оптимальность решения задачи о назначениях не нарушается при уменьшении или увеличении элементов строки или столбца на одну и ту же величину. Решение считается оптимальным, если все измененные таким образом затраты с_ij ≥ 0 и можно отыскать такой набор х_ij  для которого суммарные затраты раны 0 [5].

     1.4 Построение экономико-математической модели

транспортной  задачи 

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

 

     Решение

     Методом минимального элемента составляем начальный план перевозок. Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок с_ij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс продолжается до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m+n-1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.

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

     Таблица 1.4 – Распределение поставок

 

      Для каждой заполненной клетки составляем уравнение потенциалов:

u₁ + v₁ = 11

u₁ + v₄ = 15

u₂ + v₂ = 5

      , где u_i – номер строки, а v_j- номер столбца

U₃ + v₂ = 6

u₃ + v₃ = 8

u₃ + v₄ = 14

     Решая систему уравнений получаем:

u₁ = 0 – берем произвольно

u₂ = 2

u₃ = -1

v₁ = 11

v₂ = 7

v₃ = 9

v₄ = 15

     Составим  разности потенциалов  для свободных  клеток:

Δ₁₂ = (u₁ + v₂) – c₁₂ = 0+7-7 = 0

Δ₁₃ = (u₁ + v₃) – c₁₃ = 0+9-12 = -3

Δ₂₁ = (u₂ + v₁) – c₂₁ = 2+11-9 = 4

Δ₂₃ = (u₂ + v₃) – c₂₃ = 2+9-16 = -5

Δ₂₄ = (u₂ + v₄) – c₂₄ = 2+15-10 = 7

Δ₃₁ = (u₃ + v₁) – c₃₁  = -1+11-13 = -3

     Так как, Δ₂₁, Δ₂₄,  > 0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.

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

     Для свободной клетки (2;4), имеющей положительную  оценку ( ) строится цикл (таблица 1.5):

     Таблица 1.5 – Построение цикла

 

     У вершин со знаком (-) выбираем минимальный груз, он равен 50. Его прибавляем к грузам, стоящих у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл (рисунок 1.1). 

                                        30                                                  60

       

                 120                                                

     Рисунок 1.1 – Новый цикл 

     Имеем следующее распределение поставок (таблица 1.6):

     Таблица 1.6 – Распределение поставок

 

     Для каждой заполненной клетки записываем уравнение потенциалов:

u₁ + v₁ = 11

u₁ + v₄ = 15

u₂ + v₂ = 5

                , где u_i – номер строки, а v_j- номер столбца

u₂ + v₄ = 10

u₃ + v₂ = 6

u₃ + v₃ = 8 

     Решая систему уравнений получаем: