Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Калининградский государственный технический университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

MоP

.pdf

Скачиваний:

375

Добавлен:

03.05.2015

Размер:

1.98 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 1213 / 2213 14 15 16 17 18 19 20 21 22 > Следующая >>>

Тема6. Двойственностьвлинейномпрограммировании

121

______________________________________________________________________________________________

6.2.13.

6.2.14.

z =

4x1

→ min;

z =

4x2

→ max;

+ 4x2

+ 4x3 = 6,

4x1

x2 + x3 = 2,

4x1

≤ 4,

- 4x2

≤ 4,

-4x2 + 3x3 ≥ 4,

3x1

≥ 7,

xj≥0, j=

1,3.

6.2.15.

6.2.16.

z =

-4x1

- 2x3

→ max;

z =

- 3x2

4x2

+ 3x4 → min;

3x1

+ 2x3 = 5,

= 4,

4x1

x2 + 2x3 = 7,

4x3 + x4 = 5,

≥ 4,

2x2 - x3

≥ 2,

xj≥0, j=

1,3.

1,4.

6.2.17.

6.2.18.

z =

x2 -

→ min;

z =

4x1

- 3x3

→ max;

4x3 + 4x4 ≥ 8,

+ 4x2

≤ 4,

x2 + 2x3

- 4x4 = 4,

3x2 - x3 ≤ 5,

= 7,

+ 4x3 ≥ 5,

xj≥0, j=

1,4.

1,3.

6.2.19.

6.2.20.

z =

3x1

+ 2x3

+ 4x4 → min;

z =

4x3

→ max;

= 6,

-3x1

+ 3x3

+ x4 = 3,

3x2 - x3

≥ 8,

3x1

≥ 3,

+ x4 = 4,

x2 + 2x3

= 3,

xj≥0, j=

1,4.

6.2.21.

6.2.22.

z =

3x1 + 2x2

→ min;

z =

-2x2 + 4x3 → max;

+ 3x2 + 3x3 ≤ 7,

+ 4x2 + 3x3 = 7,

-4x1

+ 3x2 + 3x3 ≥ 4,

2x2 + 4x3 ≥ 6,

xj≥0, j=

1,3.

6.2.23.

6.2.24.

z =

4x1 - 4x2 → max;

z =

x2 - 2x3 → min;

+ 2x2 ≤ 5,

+ 3x2 + 3x3 ≤ 6,

3x1

+ x2 ≥ 0,

-x1

+ 4x2 + 3x3 ≥ 6,

xj≥0, j=

1,2.

1,3.

6.2.25.

6.2.26.

z =

-2x1

+ 2x3

→ min;

z =

2x1

+ 4x4 → min;

= 2,

+ x2

= 5,

2x1

+ 4x3 ≥ 4,

-x3 + 2x4 ≥ 4,

x2 - 3x3 = 3,

-4x3 + x4 ≥ 6,

xj≥0, j=

1,3.

1,4.

6.2.27.

6.2.28.

z =

-2x2 +

→ min;

z =

3x2

→ min;

+ x2 + 3x3 ≤ 5,

2x1

- 2x3 ≤ 3,

3x1

+ 3x2 + 4x3 ≥ 6,

x2 + x3 = 5,

xj≥0, j=

2x1

≥ 5,

1,3.

xj≥0, j=

1,3.

6.2.29.

6.2.30.

z =

-3x1 - 3x2

→ max;

z = -2x1 +

→ max;

- x2

= 3,

4x1

+ 3x2 + x3 = 5,

3x3 = 6,

3x1

+ 3x2

≥ 3,

3x2 + 3x3 ≥ 3,

xj≥0, j=

1,3.

xj≥0, j=

1,3.

122 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

6.2.31.

6.2.32.

z =

4x1

→ min;

z =

+ 3x3 → min;

2x2

≤ 5,

+ 2x2 - 4x3 = 0,

+ 3x3 = 8,

4x2 - x3 ≥ 7,

2x2

≥ 0,

xj≥0, j=

1,3.

xj≥0, j=

1,3.

6.2.33.

6.2.34.

z =

+ 4x3

-x3 + 3x4 → max;

z =

4x1 + 2x2 + x3

→ min;

= 7,

2x2 + 3x3 ≥ 6,

+ 4x4 = 5,

+ 2x2 + 3x3 = 7,

4x3 + 3x4 ≥ 0,

xj≥0, j=

1,3.

1,4.

6.2.35.

6.2.36.

z =

2x1 - 4x2

→ min;

z = -3x1 + 4x2 + 2x3

→ min;

2x2 - 2x3 = 4,

4x1

+ x2 + 2x3 = 4,

+ x2

x3 ≥ 0,

3x1

+ 4x3 ≥ 5,

= 8,

xj≥0, j=

1,3.

xj≥0, j=

1,3.

6.2.37.

6.2.38.

z =

4x1

+ 2x3 → min;

z =

3x1

+ 3x3 → min;

3x1

-3x2 + 3x3 = 0,

2x1

- x2

≤ 4,

+ 4x2

+ 4x3 ≤ 6,

4x1

+ 3x3 = 7,

-4x1

≥ 4,

4x2 - x3 ≥ 5,

xj≥0, j=

1,3.

6.2.39.

6.2.40.

z =

4x2 → min;

z =

2x1

- 2x3

→ min;

2x1

- 3x2 = 3,

- 4x4 = 7,

2x1

+ x2 ≥ 3,

x2 + 2x3

= 7,

xj≥0, j=

4x3 - 3x4 ≥ 0,

1,2.

xj≥0, j=

1,4.

6.2.41.

6.2.42.

z = -3x1

- 4x3 → max;

z =

4x3

+ x4 → min;

-x1

+ 2x2

- x3 ≤ 4,

3x2 - 3x3

≥ 0,

2x1

= 0,

4x2

+ x4 = 7,

2x2 + 2x3 ≥ 4,

- 2x3

= 8,

xj≥0, j=

1,3.

1,4.

6.2.43.

6.2.44.

z =

-3x2

+ 3x3

→ min;

z =

x2 + 2x3

→ max;

-4x1

+ 3x3

≥ 7,

-2x2 + x3

≥ 2,

3x1

+ x3

≥ 3,

-x2

+ x4 = 7,

+ x4 = 5,

+ 3x3

= 5,

xj≥0, j=

1,4.

6.2.45.

6.2.46.

z =

-4x2 + 4x3 → min;

z =

+ 3x2

4x2 + 3x3 → max;

4x1

- 4x2

= 5,

≤ 4,

2x1

- x2

≥ 4,

2x1

4x2

≥ 4,

x3 = 6,

+ x3 = 7,

xj≥0, j=

1,3.

6.2.47.

6.2.48.

z =

x1 + 3x2

→ min;

z =

3x1 +

x2 → max;

+ 3x3

+ 4x4 = 7,

3x1

+ 3x2 ≤ 6,

= 0,

2x1

+ 4x2 ≥ 0,

x3 + 3x4 ≥ 4,

xj≥0, j=

1,2.

1,4.

Тема6. Двойственностьвлинейномпрограммировании

123

______________________________________________________________________________________________

6.2.49.

6.2.50.

z =

3x3

→ min;

z = 2x1 + 3x2 → min;

+ x4 = 2,

3x1

+ 2x2 = 7,

-3x2 + 2x3

≥ 5,

+ 3x2 ≥ 4,

+ 3x3

≥ 5,

xj≥0, j=

1,2.

xj≥0, j=

1,4.

6.2.51.

6.2.52.

z =

2x1 + 3x2 + 2x3 → max;

z =

3x2

-x2

→ max;

2x2 - x3 ≥ 8,

+ 2x3

+ x4 = 5,

+ x2 + 4x3 = 8,

= 6,

xj≥0, j=

2x2

+ 3x3

≥ 7,

1,3.

xj≥0, j=

1,4.

6.2.53.

6.2.54.

z =

+ 4x3

2x4 → min;

z = -3x1 - 2x2

→ max;

= 4,

+ x2

= 2,

- 2x4 = 4,

2x2

x3 + 2x4 = 5,

x3 + 4x4 ≥ 5,

+ 2x4 ≥ 8,

xj≥0, j=

1,4.

xj≥0, j=

1,4.

6.2.55.

6.2.56.

z =

4x1

x3 + 3x4 → min;

z =

x2 + x3

2x3

- x4 → max;

+ x2

- 4x3

≥ 6,

4x1

= 0,

-x1

= 6,

+ 4x4 ≥ 6,

xj≥0, j=

4x3 + x4 = 6,

2x1

- 2x4 ≥ 6,

1,4.

xj≥0, j=

1,4.

6.2.57.

6.2.58.

z =

2x1 -

→ max;

z =

4x2 + 3x3 → max;

-x1

3x2

≤ 8,

3x2

+ x3 = 6,

+ 3x2

+ x3 = 3,

2x1

≤ 0,

-4x1

≥ 4,

+ 4x2

≥ 8,

xj≥0, j=

1,3.

xj≥0, j=

1,3.

6.2.59.

6.2.60.

z =

-4x1 + 4x2

→ max;

z =

-3x2

- 3x3

→ max;

-4x1

+ 4x2

≥ 0,

2x2 - 2x3

≥ 0,

2x1

+ 4x2 + x3 = 8,

+ x4 = 4,

xj≥0, j=

≥ 5,

1,3.

xj≥0, j=

1,4.

6.2.61.

6.2.62.

z =

-2x2 + 2x3 → min;

z =

3x1

+ 2x3

→ max;

-3x1

+ 3x2

≥ 0,

-x2

+ 3x4 ≥ 3,

-x1

+ 3x2 + x3 = 5,

- 2x2

x3 + 2x4 = 8,

xj≥0, j=

= 3,

1,3.

xj≥0, j=

1,4.

6.2.63.

6.2.64.

z =

-3x1

- x3

→ max;

z =

3x1 + 2x2

→ min;

-3x1

+ 4x2

= 6,

≥ 0,

-x1

+ 4x3 ≤ 4,

4x1

+ x2

x3 = 7,

4x2 - 2x3 ≥ 5,

= 7,

xj≥0, j=

1,3.

6.2.65.

6.2.66.

z =

2x1 +

→ min;

z =

4x2

→ min;

- 4x3 = 7,

- x2 + 2x3 = 4,

= 7,

x2 + 3x3 ≥ 3,

x2 - 3x3 ≥ 4,

xj≥0, j=

1,3.

xj≥0, j=

1,3.

124 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

6.2.67.

6.2.68.

z =

-2x2

+ 3x3

→ min;

z =

2x3

+ x4 → min;

3x1

= 4,

3x1

+ x2

+ 4x4 ≥ 5,

2x1

x2 + 4x3 = 8,

2x1

= 7,

+ 4x3 ≥ 6,

x3 - 3x4 = 8,

xj≥0, j=

1,3.

1,4.

6.2.69.

6.2.70.

z =

-3x3

x4 → max;

z =

3x1

→ min;

x2 + 4x3

= 6,

3x1

= 8,

+ 4x3

+ x4 = 8,

4x1

x2 - x3 = 6,

4x1

≥ 6,

- 2x3 ≥ 7,

xj≥0, j=

1,4.

1,3.

6.2.71.

6.2.72.

z =

2x1

+ 2x3

→ min;

z =

x1 + 2x2 → min;

3x1

3x2

≤ 4,

+ x2 = 8,

+ 2x2

≥ 5,

3x1

≥ 5,

-4x1

= 6,

xj≥0, j=

1,2.

xj≥0, j=

1,3.

6.2.73.

6.2.74.

z =

4x1 + 2x2 +

→ min;

z =

3x1 + 2x2 + x3

→ min;

4x1

- x2 + x3 = 8,

4x1

+ x2 + 4x3 = 8,

2x1

+ x2

≥ 6,

3x1

+ 3x2 + 4x3 ≥ 7,

xj≥0, j=

1,3.

6.2.75.

6.2.76.

z =

4x2 - 4x3 → min;

z = -2x1

+ 2x3 → max;

- x2 + 3x3 = 6,

+ x2 + x3 = 5,

3x1

+ 4x2 + 2x3 ≥ 7,

4x1

+ 3x3 ≥ 6,

xj≥0, j=

1,3.

6.2.77.

6.2.78.

z =

4x3

→ max;

z =

2x1 +

→ max;

x2 - 3x3

+ x4 = 5,

3x1

+ 2x2 + 3x3 = 5,

= 8,

+ x2 - x3 ≥ 0,

-x3 + 2x4 ≥ 0,

xj≥0, j=

1,3.

1,4.

6.2.79.

6.2.80.

z =

2x1

+ 2x3

→ min;

z =

3x2 + 3x3

→ min;

- 3x2

= 6,

+ x3

= 6,

4x3 = 0,

- 2x4 ≥ 6,

4x2 + 2x3 ≥ 8,

2x2

+ 4x4 ≥ 4,

xj≥0, j=

1,3.

1,4.

6.2.81.

6.2.82.

z =

3x1

x4 → max;

z =

3x1

+ 2x3 → max;

4x2 + 3x3

≥ 8,

4x1

+ 4x3 ≤ 7,

4x2 - 3x3

≥ 6,

4x1

= 4,

+ x4 = 5,

+ 3x3 ≥ 0,

xj≥0, j=

1,4.

1,3.

6.2.83.

6.2.84.

z = 3x1 + 2x2 → min;

z =

2x3 → min;

-3x1

+ 3x2 = 5,

-4x1

- 2x2

+ 2x3 ≤ 5,

-3x1

+ 4x2 ≥ 0,

2x1

= 0,

xj≥0, j=

-2x2 + 2x3 ≥ 5,

1,2.

xj≥0, j=

1,3.

Тема6. Двойственностьвлинейномпрограммировании

125

______________________________________________________________________________________________

6.2.85.

6.2.86.

z =

-x1 + 2x2

→ min;

z =

-3x2

- 4x3

→ max;

-4x1

- 2x2

- 4x3 ≤ 6,

3x1

- x2

≤ 6,

4x1

≤ 4,

3x1

≥ 4,

x2 + 4x3 ≥ 8,

4x2 + x3 = 7,

xj≥0, j=

1,3.

6.2.87.

6.2.88.

z =

2x3 + 2x4 → max;

z =

3x1 + 2x2

→ min;

- x2

x3 + x4 = 6,

3x1

+ x2

= 6,

≥ 3,

+ 4x3 ≤ 8,

-2x1

+ 4x2

≥ 4,

4x3 ≥ 7,

xj≥0, j=

1,4.

xj≥0, j=

1,3.

6.2.89.

6.2.90.

z =

+ x2

4x2

→ min;

z =

-3x2

- x4 → max;

= 8,

x2 + x3

- 4x4 = 6,

3x1

x3 ≤ 7,

= 6,

- 4x3 ≥ 0,

x3 - 3x4 ≥ 3,

xj≥0, j=

1,3.

1,4.

6.2.91.

6.2.92.

z =

4x1

2x2 + 2x3 → min;

z =

x2 - 3x3

→ max;

+ x2 + x3 = 5,

4x1

+ x4 = 3,

2x1

+ 4x3 ≥ 8,

+ 2x3

≥ 7,

xj≥0, j=

4x1

≥ 5,

1,3.

xj≥0, j=

1,4.

6.2.93.

6.2.94.

z =

-3x1

+ 3x4 → min;

z =

2x2 - 4x3

→ max;

2x1

- 2x4 ≥ 6,

- 2x3

= 6,

+ x2

x3 + 2x4 = 7,

+ 2x4 = 0,

= 5,

x3 + 4x4 ≥ 7,

xj≥0, j=

1,4.

xj≥0, j=

1,4.

6.2.95.

6.2.96.

z =

-3x1

+ 3x3 → max;

z = -3x1 + 2x2

→ min;

2x1

2x2 + 4x3 ≤ 5,

2x1

+ 3x3

≥ 8,

- 2x2

≤ 8,

4x1

x2 - x3

+ x4 = 0,

- 3x3 ≥ 5,

= 7,

xj≥0, j=

1,3.

1,4.

6.2.97.

6.2.98.

z =

4x1

+ x3

→ min;

z =

2x1

+ 2x3

→ min;

= 5,

4x1

- 4x2 + x3 = 8,

3x2 - x3 = 3,

3x1

+ 4x2 + 3x3 ≥ 7,

-2x2 + 3x3 ≥ 4,

xj≥0, j=

1,3.

xj≥0, j=

1,3.

6.2.99.

6.2.00.

z =

- x4 → min;

z =

-2x2 + 4x3 → min;

2x1

3x2 + x3

= 5,

-2x1

4x2 + x3 = 5,

- 2x2

≥ 0,

+ 4x3 ≤ 4,

+ x4 = 6,

4x1

- 2x2

≥ 7,

xj≥0, j=

1,4.

xj≥0, j=

1,3.

126 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

Тема 7. Решение задач транспортного типа

7.1. Задачи линейного программирования транспортного типа

Многие экономические задачи сводятся к задачам транспортного типа, которые являются задачами линейного программирования и могут быть решены сим- плекс-методом. Однако количество переменных и ограничений транспортной задачи является большими величинами, с другой стороны – ограничения транспортной задачи являются простыми (коэффициенты при переменных равны 1). Поэтому для решениятакихзадачразработаныболеепростыеточныеметодырешения.

Типы транспортных задач.

Имеются m поставщиков однородной продукции с известными запасами этой продукции и n потребителей этой продукции с заданными объёмами потребления. Известны также удельные затраты на перевозку.

Если сумма объёмов запасов продукции равна объёму потребления всех потребителей, то такая задача называется закрытой транспортной задачей (то

есть	m	А	=	n		), в противном случае – открытой. Для решения транспорт-
есть	∑	А	=	∑ B		), в противном случае – открытой. Для решения транспорт-
	i =1	i		j =1	j

ной задачи необходимо, чтобы она была закрытой.

Открытую транспортную задачу можно преобразовать в закрытую следующим образом.

m		n	. В этом случае необходимо ввести фиктивного n+1
Пусть ∑ Аi	>	∑ B j	. В этом случае необходимо ввести фиктивного n+1
i =1		j =1
				m			n
потребителя с объёмом потребления				∑	А	−	∑ B	j	. Удельные затраты на пере-
				i =1	i		j =1	j
				i =1			j =1

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

Тема7. Решениезадачтранспортноготипа

127

______________________________________________________________________________________________

. В этом случае необходимо ввести фиктивного m+1

Пусть ∑

∑

j =

i =1

поставщика с объёмом запасов

−

А . Удельные затраты на перевозку

∑

j =1

i =1

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

В закрытой транспортной задаче все ограничения записываются в виде уравнений:

z =

c ij x ij → min ,

∑

i = 1

= 1

I .

∑ x ij

= A i ;

i = 1 , m ,

= 1

II .

∑

x ij

= B j ;

j = 1 , n

= 1

III .

x ij ≥

0 ,

i = 1 , m

; j = 1 , n .

Теорема 1. Закрытая транспортная задача всегда имеет решение. Теорема 2. Если объёмы запасов продукции и объёмы потребностей яв-

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

7.2. Методы построения исходного распределения транспортных задач

Для решения задач симплекс-методом необходимо наличие исходного опорного плана. Решение транспортной задачи также начинается с построения исходного опорного плана, который в транспортной задаче называется исход-

ным распределением.

Определим, какое количество базисных переменных должно быть в опорном плане. Так как ограничения транспортной задачи содержат n+m уравнений, то количество базисных переменных также должно быть n+m, если все уравнения являются линейно независимыми. Однако в транспортной задаче эти

128 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

уравнения линейно зависимы. Чтобы показать это, найдём суммы всех ограни-

чений (I) и (II).

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

неизвестных переменных х, а в правой части в одном из уравнений –			m	А , а в
			∑	А , а в
			i =1	i
другом –	n	. Поскольку задача закрытая, то эти суммы равны, то есть мы по-
другом –	∑ B j
	j =1

лучили два одинаковых уравнения (линейно зависимых). Удалив любое из ограничений, мы получим систему из m+n-1 линейно независимых уравнений. Таким образом, количествопеременных вопорномпланедолжнобытьm+n-1.

Пример. Имеются три поставщика и четыре потребителя однородной продукции. В следующей таблице заданы объёмы запасов, объёмы потребления и удельные затраты на перевозку продукции.

Вj	70		30	80	60
Аi
100		8	2	0	1

80		3	4	2	3

120		1	4	1	2

Найти такие объёмы перевозки, при которых общие затраты на перевозку будут минимальными.

Решение.

Проверяем тип транспортной задачи. Определяем объём запасов всех поставщиков (100+80+120=300) и объём потребления всех потребителей (70+30+80+60=240). Запасы продукции больше, чем потребности в ней на 300– 240=60 единиц. Для того чтобы преобразовать эту задачу в закрытую, необходимо ввести фиктивного пятого потребителя с объёмом потребностей 60 единиц. Удельные затраты на перевозку продукции от поставщиков к фиктивному потребителю полагаем равными нулю.

Тема7. Решениезадачтранспортноготипа

129

______________________________________________________________________________________________

Вj	70		30	80	60	60
Аi
100		8	2	0	1	0

80		3	4	2	3	0

120		1	4	1	2	0

Существует несколько методов построения исходного распределения транспортных задач. Рассмотрим два таких метода.

Метод северо-западного угла. При построении исходного распределения с помощью данного метода, из оставшихся клеток выбирается левая верхняя клетка (северо-западная). На первом этапе выбирается клетка (1,1). В эту клетку записывается объём поставки х11= min {А1,В1}. Величины А1 и В1 уменьшаются на данную величину. Ту строку или столбец, где будет получен 0, удаляют из рассмотрения. Затем из оставшихся клеток, рассматривают левую верхнюю клетку и поступают аналогично. Продолжая данный процесс, мы заполним клетку (m,n), причем удалим из рассмотрения и строку и столбец. Если в процессе заполнения клеток придётся вычеркнуть и строку, и столбец, то мы получим вырожденное распределение (количество занятых клеток меньше, чем m+n-1). Чтобы этого не произошло, из рассмотрения удаляем что–то одно: или строку, или столбец, а оставшийся столбец или строку считают с нулевой потребностью или запасами. Вычислим значение целевой функции для исходного распределения: z=8 × 70 + 2 × 30 + 2 × 80 + 2 × 60 = 900.

Вj	70		30		80		60		60
Аi
100	70	8	30	2	0	0		1	0
	70		30		0
80		3		4	80	2	0	3	0
					80		0
120		1		4		1	60	2	0
							60		60

Метод минимального элемента. Метод северо-западного угла при заполнении клеток абсолютно не учитывает удельные затраты на перевозку, поэтому значение целевой функции может быть далёким от оптимального и, воз-

130 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

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

Вj	70	30		80		60		60
Аi
100	8		2	80	0		1	0
				80				20
80	3	30	4		2	10	3	0
		30				10		40
120	1		4		1	50	2	0
	70					50

Вычислим значение целевой функции при построенном исходном рас-

пределении: z = 4 × 30 + 3 × 10 + 1 × 70 + 2 × 50 = 320. Значение целевой функции при исходном распределении, построенным методом минимального элемента (320) значительно меньше, чем значение целевой функции при исходном распределении, построенным методом северо-западного угла (900).

7.3. Метод потенциалов решения транспортной задачи

После построения исходного распределения необходимо определить является ли данное распределение оптимальным, и, если нет, то перейти к другому «лучшему» распределению. Продолжая данный процесс, найдём оптимальное решение транспортной задачи. Для этих целей используется метод потенциалов, который основан на следующей теореме.

Теорема. Если для некоторого распределения транспортной задачи выполняются условия: а) ui+vj=сij – для занятых клеток; б) ui+vj ≤сij – для свободных клеток, то данное распределение является оптимальным.

Величины ui называют потенциалами строк, а величины vj называют потенциалами столбцов.

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 1213 / 2213 14 15 16 17 18 19 20 21 22 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
03.05.2015802.3 Кб20moya_praktika_2013_2.docггггггггггггггггггг.doc
#
02.09.2019386.05 Кб6MSFO_kontrolnaya_rabota_1.doc
#
03.05.2015145.92 Кб17MUKr_NIR14.doc
#
11.03.2016137.01 Кб38MUROV_V_M__NORDIN_V_V_Uch_-_metod_posobie_po_kursovoy_rabote_LOGISTIKA_Skorr.docx
#
13.11.2019496.94 Кб4My_hobby.docx
#
03.05.20151.98 Mб375MоP.pdf
#
03.05.2015437.11 Кб26ocenka_teh_sost_maket_.pdf
#
12.08.2019175.1 Кб4Oforml_Text.doc
#
14.11.2018167.42 Кб10Oglavlenie.doc
#
13.11.201872.84 Кб5otkrytie_pekarni.docx
#
11.03.2016494.08 Кб72Otvety_na_fizkulturu.doc

Вj	70		30		80		60		60
Аi
100	70	8	30	2	0	0		1	0
	70		30		0
80		3		4	80	2	0	3	0
					80		0
120		1		4		1	60	2	0
							60		60

Вj	70	30		80		60		60
Аi
100	8		2	80	0		1	0
				80				20
80	3	30	4		2	10	3	0
		30				10		40
120	1		4		1	50	2	0
	70					50

Вj	70		30		80		60		60
Аi
100	70	8	30	2	0	0		1	0
	70		30		0
80		3		4	80	2	0	3	0
					80		0
120		1		4		1	60	2	0
							60		60

Вj	70	30		80		60		60
Аi
100	8		2	80	0		1	0
				80				20
80	3	30	4		2	10	3	0
		30				10		40
120	1		4		1	50	2	0
	70					50

Вj	70		30		80		60		60
Аi
100	70	8	30	2	0	0		1	0
	70		30		0
80		3		4	80	2	0	3	0
					80		0
120		1		4		1	60	2	0
							60		60

Вj	70	30		80		60		60
Аi
100	8		2	80	0		1	0
				80				20
80	3	30	4		2	10	3	0
		30				10		40
120	1		4		1	50	2	0
	70					50