Целевая функция (1), ограничение (2), (3) со знаком 

условный потребитель (n +1): b_n+1 =  а_i -  b_j

x₁, …, x_{2, n+1}, … x_{m, n+1} – недовостребованное количество груза

если t_ij  c_ij – оптимальный план изменится.

3. Модель перевозки взаимозаменяемых грузов.

Если груз полностью взаимозаменяемый, то его переводят к условным однородным единицам – коэффициентам:

B₁, В₂ …, В_m – количество груза, m-видов груза;

k₁, k₂ …, k_m – коэффициенты перевода груза в условные единицы;

k₁  B₁, k₂  B₂, … k_m  B_m – условные единицы.

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

ПРИМЕР:

Допустим А₁, А₂ – поставщики; B₁, В₂, В₃ - потребители.

Запасы груза:

Поставщики	Марка	Количество
А1	М 300 М 500	200 100
А2	М 300 М 500	300 400

Спрос:

Потребители	Марка	Количество
B1	М 300 М 500	300 250
B2	М 300 М 500	200 100
B3	М 500	150

Транспортные затраты:

	B1	B2	B3
А1
А2

Модель транспортной задачи:

B₁ B₂ B₃

Потребители Запас			М 300 300	М 500 250	М 300 200	М 500 100	М 500 150
А1	М 300 М 500	200	4	М	5	М	М
		100	М	4	М	5	6
А2	М 300 М 500	300	7	М	8	М	М
		400	М	7	М	8	9

4. Задача оптимального назначения.

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

Постановка задачи: пусть имеется n работ (1, 2,…, j,…, n) и m специалистов (1, 2,…, i,…, m). с_ij – эффективность выполнения j-ой работы i-ым специалистом.

Требуется оптимально распределить специалистов по работам, с целью получения максимального суммарного эффектов при выполнении условий:

1) каждую работу выполняет только один специалист;

2) каждый специалист назначается только на одну работу.

Рассмотрим случай, когда m = n – закрытая модель.

x_ij – переменная выбора, она равна:

x_ij = 1, если специалист выполнит j-ую работу;

х_ij = 0, если специалист не выполнит j-ую работу (не назначен).

z =  max (1)

, j = (2)

, i = (3)

х_ij  0 (4)

Это транспортная модель. А если свободные члены целые числа, то переменные тоже целые числа.

Виды открытой модели:

Если m > n, кто-то останется без работы:

(1), (2), (4) и (3)

Если m < n, работы больше, чем специалистов:

(1), (3), (4) и (2)

ПРИМЕР:

Имеется три специалиста и столько же работ. Производительность каждого специалиста по каждой работе:

Специалисты	Производительность по работам
	№1	№2	№3
1 2 3	20 17 18	15 12 15	10 15 14

х_ij – i-ый специалист выполняет j-ую работу.

Модель:

z = 20  х₁₁ + 15  х₁₂ + 10  х₁₃ + 17  х₂₁ + 12  х₂₂ + 15  х₂₃ + 18  х₃₁ + 15  х₃₂ + 14  х₃₃  max

требование, что каждый специалист выполняет одну работу:

x₁₁ + х₁₂ + х₁₃ = 1,

x₂₁ + х₂₂ + х₂₃ = 1,

x₃₁ + х₃₂ + х₃₃ = 1.

требование, что каждая работы выполнима:

x₁₁ + х₂₁ + х₃₁ = 1,

x₁₂ + х₂₂ + х₃₂ = 1,

x₁₃ + х₂₃ + х₃₃ = 1.

Переменных 9 штук.

ПРИМЕР:

Имеется 3 группы взаимозаменяемого оборудования, на котором обрабатывается 3 вида изделий: № 1, № 2, № 3. Даны нормы расхода времени на одно изделие, фонд времени и прибыль от реализации одного изделия.

Группа оборудования	Нормы времени			Фонд времени
	№ 1	№ 2	№ 3
1	10	5	15	150
2	15	10	20	300
3	20	25	50	350
Прибыль	10	20	30

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

Группа оборудования	Количество изделий
	№ 1	№ 2	№ 3
1	15	30	10
2	20	30	15
3	25	20	10

Модель: х_ij – выбор; i – оборудование; j – изделие.

z = 10  15  x₁₁ + 10  20  x₂₁ + 10  25  x₃₁ + 20  (30  x₁₂ + 30  x₂₂ + 20  x₃₂) + 30  (10  x₁₃ + 15  x₂₃ + 10  x₃₃)  max

x₁₁ + x₁₂ + x₁₃ = 1,

x₂₁ + х₂₂ + х₂₃ = 1,

x₃₁ + х₃₂ + х₃₃ = 1.

x₁₁ + х₂₁ + х₃₁ = 1,

x₁₂ + х₂₂ + х₃₂ = 1,

x₁₃ + х₂₃ + х₃₃ = 1.

x_ij  0