2.2. Методические рекомендации

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

Если величина фиктивных тарифов превышает максимальный из реальных тарифов задачи [с* >maxcij (i = l,n;j = l,m)], to методы минимального элемента и Фогеля позволяют получить более дешевые планы перевозок, чем в случае с нулевыми фиктивными тарифами.

Задача №1

Найти тремя методами опорный план ТЗ, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 125, 90, 130, 100 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие:

5 8 1 2

2 5 4 9

9 2 3 1

Решение

Проверка сбалансированности задачи показывает, что суммарный объем запасов равен суммарному объему потребностей, т.е. введение фиктивных столбцов или строк не потребуется:

Запасы потребности

210 + 170 + 65 = 125 + 90 + 130 + 100.

445 ед.товара 445 ед.товара

Результаты нахождения опорного плана различными методами представлены в табл. 1, 2 и 3.

Таблица 1 - Транспортная таблица с опорным планом северо-западного угла

Пункты потребления, В;
Пункты отправления, Aj	Bi	В2	В3	в4	Запасы, ед. продукции
Ai	125 5	85 8	1	2	210/85/0
А2	2	5 5	130 4	35 9	170/165/35/0
А3	9	2	3	65 1	65/0
Потребность, ед. продукции	125/0	90/5/0	130/0	100/65/0

Опорный план Х(сзу), найденный методом северо-западного угла

ХСЗУ =

125 85 0 0 0 5 130 35 0 0 0 65

[ед. товара]

Соответствующая ЦФ (общие затраты на перевозку)

L(X)= 125*5+85*8+5*5+130*4+35*9+65*1=2230 [руб.]

Таблица 2 - Транспортная таблица с опорным планом минимального элемента

Пункты потребления, В;
Пункты отправления, Aj	Bi	В2	В3	В4	Запасы, ед. продукции
Ai	5	45 8	130 1	35 2	210/80/45/0
А2	125 2	45 5	4	9	170/45/0
А3	9	2	3	65 1	65/0
Потребность, ед. продукции	125/0	90/45/0	130/0	100/35/0

Опорный план, найденный методом минимального элемента

^хмэ =

0 45 130 35 125 45 0 0 0 0 0 65

[ед. товара],

L(Х_мэ) =1100 [руб.]

Таблица 3 - Транспортная таблица с опорным планом Фогеля

	в1		в2		в3		в4	вi		Штрафы строк, dj
A1	5		8		100 1		100 2	210/110/0		1	1	1	7
А2	125 2		25 5		20 4		9	170/45/25/0		2	1	1	1
А3	9		65 2		3		1	65/0		1	1	—	—
Аi		125/0		90/25/ 0		130/20 /0	100/0
Штрафы столбцов,		3		3		2	1
		—		3		2	1
		—		3		3	7
		—		3		3	—

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

d ₁ столбца = d ₂ столбца = 3

Минимальные тарифы в этих столбцах также совпадают

^С₂₁=^С₃₂=3

Поэтому необходимо сравнить суммарные штрафы dj клеток (2,1) и (3,2)

d₂₁ = d₂ строки + d₁ столбца = 2 + 3 = 5;

d₃₂ = d_З строки+ d₂ столбца =1 + 3 = 4.

Т.к. d_2i > d₃₂, то выбираем на первом шаге для заполнения клетку (2,1).

Опорный план Хф, найденный методом Фогеля

L(Х_мэ) = 895 [руб.].

Х ф=

0 0 100 100 125 25 20 0 0 65 0 0

Варианты индивидуальных заданий для практических работ

№ варианта	Графический метод решения задач линейного программирования	Нахождение опорных планов
1	1,2,3	1
2	4,5,6	2
3	2,8,9	3
4	1.2,9	1
5	1,2,8	2
6	1,2,7	3
7	1,2,6	1
8	1,2.5	2
9	1,2,4	3
10	2.4,6	1
11	2,4,7	2
12	2,5.8	3
13	2,4.7	1
14	2,4,9	2
15	3,5.7	3
16	4,6,8	1
17	5.8,9	2
18	3,6,9	3
19	6,8,9	1
20	6,7.8	2

Варианты задач линейного программирования для решения графическим методом

Задач 1 L (X) = 4x1 - Зх2 —» max (min) 5х1 -2х2<20 х1+2х2>10 -7х1+10х2 <80, х1,х2 >0.	Задача 2 L(X )= 2x1 + 5х2 —» max (min) 2х1-х2>6 х1+2х2>5 4х1+х2 >8 -х1 +2х2 >6 х1,х2 >0
Задача 3 L(X )= х1 + 2x2 —» max (min) -х1+3х2>10 х1 +х2 <6, x1+4x2 >3, -х1+4х2 >2, x1,x2 >0.	Задача 4 L(X) = -2x1 + 5x2 —» max (min) -3x1 +2x2 <12, х1 +2x2= 8 x1 +х2 >5, x1,x2 >0
Задача 5 L(X )= x1 + 6x2 —» max (min) х1+2х2<10, 3х1-3x2 >6, 2х1+3х2<6, 3х1+х2>4, х1,x2 >0.	Задача 6 L(X) = -3х1 - 2x2 —» max (min) х1-х2>3, 2х1+2х2>2, х1+х2 >6, -2х1 +6x2 <20, x1,x2 >0.
Задача 7 L(X )= х1 + 6x2 —» max (min) -2х1+12х2 >8, 4х1+2х2<10, 3х1-4х2>2, 4х1+5х2>8, х1,x2 >0.	Задача 8 L (X ) = 4х1 + 2x2 —» max (min) х1+2x2 >7, 2х1+x2 >8, -х1+2x2 <6, -2х1+8х2>4 х1,x2 >0
Задача 9 L (X ) = 3x1 + 4x2 —» max (min) х1 +2x2 >8, 4х1+4х2>18, -х1+х2<1, х2=2, x1,x2>0.