Файл: Постнов Ю.И. Линейное программирование в сельском хозяйстве.pdf

§ 7

БОЛЕЕ СЛОЖНЫЙ ПРИМЕР

Р а с с м о тр и м

случай , ко гд а

по условию з а д а ч и им еется

три с к л а д а

и п я т ь м агази н ов .

Д а н н ы е з а д а ч и и исходны й

п л а н

п еревозок

п р е д с т а в л е ­

ны в т а б л и ц е

75.

Таблица 75

1

2

3

4

5

И м е е т ­

ся

1

4

1

3

4

4

6 0

2 2

3 8

2

2

3

2

2

3

3 5

-

2

7

2 0

8

3

3

5

2

4

4

4 0

-

4

1 0

3 0

2 2

4 5

2 0

1 8

3 0

1 3 5

— 4

-1

О б щ а я

стои м ость всех

п ер е в о зо к

по

этом у п л а н у

р а в н а

C = 4-22 + l - 3 8 + 3 - 7 + 2 - 2 0 + 2 - 8 + 4 -

1 0 + 4 - 3 0 = 363 руб.

Если

цены

в

к л е т к а х

с т о в а р а м и

при вести

к н у л я м ,

то

получим т а б л и ц у 76.

17-36

Д л я

улучш ени я

п л а н а

перевозок

ж е л а т е л ь н о

н екоторое

коли чество

т о в а р а

перем ести ть

в своб од н ую

к л е т к у с

н а и б о л ь ш е й

по

абсолю тн ой

велич ине о тр и ц ател ь н о й ц е ­

ной.

Т акой

кл етк о й

я в л я е т с я

тр е ть я

к л е т к а

первого

с то лб ц а с ценой

( — 5).

Ч т о б ы произвести пер ем ещ ен и е т о в а р а

в эту клетку , н а ­

до построить « кольцо »,

в к л ю ч а ю щ е е эту свобод ную к л е т ­

ку и еще,

по к р ай н ей

мере,

тр и

клетки , за н я т ы е товар о м .

П о с т р о и т ь

« кольцо »,

и м ею щ ее

ф о р м у п р я м о у го л ь н и к а , в

этом

слу ч ае

н ев о зм о ж н о .

С л е д о в а т е л ь н о ,

н а д о строить

« кольц о в о зм о ж н ы х

перем ещ ен ий » б о лее

сл о ж н о й ф о р ­

мы. Т ак о е

« кольц о »

п о к а за н о в т а б л и ц е

76.

Таблица 7G

2

3

4

5

Имеет­

ся

1

0

0

3

4

4

6 0

2 2 --------- V 3 8

2

-

4

1

о

0

0

1

3 5

2 0 ------

1 7 —

->

8

3

- 5

0

- 2

і

°

3 0

0

4 0

10

22

4 5

2 0

1 8

30

135

П о в о р о т н ы м и

к л е т к а м и « к о л ь ц а »

б у д ем н а з ы в а т ь такие

клетки , в к о то р ы х

о с у щ е с т в л я ет с я

п ер е х о д

с го р и зо н тал и

на

в е р т и к а л ь

или

н аоб орот. П р и

п ер ем ещ ен и и

н е к о то р о ­

го

ко л и ч ества

т о в а р а в свобод ную к л е т к у

по

« кольц у »

количество

т о в а р а

будет

и зм е н ят ь с я л и ш ь

в п оворотны х

к л е т к а х

и не б уд ет

и зм е н ять с я — во всех прочих к л е т к а х .

В н аш ем

п р и м ер е

в п оворотны х

к л е т к а х

п р о став л ен о

к о ­

личество

т о в а р а :

22,

38,

7,

8, 10.

Л е г к о

проверить, что в

свобод ную

к л е т к у

м о ж н о п ерем ести ть 7

еди ниц или

л ю ­

бое

коли чество , м еньш ее

7.

П р и п ерем ещ ен и и

н е о б х о д и ­

мо пом нить о том ,

чтобы

в ы п о л н я л и с ь

т р е б о в а н и я

по

ст р о к а м

и с т о л б ц а м

таб ли ц ы .

П р о и зв о д я пер ем ещ ен и е

7

еди ниц

т о в а р а ,

придем к

т а б ­

л и ц е с у л у ч ш ен н ы м

п л ан о м

п е р ев о зо к (таб л . 77).

Таблица 77

1

2

3

4

5

Имеет­

ся

1

15

0

45

0

3

4

4

60

- 5

2

- 4

0

0

0

1

35

20

15

3

7

—5

0

- 2

о

О о

40

СО

со

22

45

20

СО

!

о СО

1 135

і

5

5

і

!

і

П о это м у

п л а н у

о б щ а я

стои м ость

всех

п ер е в о зо к р а в н а :

С = 4 • 1 5 + 1 • 45 + 2 • 20 + 2 • 15 + 3 • 7 + 4 • 3 +

+ 4

• 3 0 = 3 2 8

руб.

Д а л ь н е й ш е е

у лучш ен и е

п л а н а п р о и зво д и тся ан алоги ч н о .

П р и в е д е м

его в од ной об ъ ед и н ен н ой т а б л и ц е

78.

17*

247