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

Р а с с м а т р и в а я

т а б л и ц у

62, видим , что в

к л е т к а х

ее и м е ­

ю тся

нулевы е,

о т р и ц а т е л ь н ы е

и п о л о ж и тел ь н ы е

цены.

О к а зы в а е т с я ,

что

если

некоторое коли чество то в а р а

из

к л е т о к с

нулевой

ценой

перем естить

в

к л е т к у

с

о т р и ц а ­

тельн ой

ценой,

то

о б щ а я

стоим ость

всех

перевозок

у м ен ьш и тся ,

а

если

в

кл етк у с

п о л о ж и т ел ь н о й

ценой,

то

увеличится .

Т а к

к а к

н а ш а

з а д а ч а з а к л ю ч а е т с я

в

ум еньш ении

с т о и ­

м ости

всех

перевозок ,

то

некоторое

коли чество

то в а р а

с л ед у ет

п ерем ести ть

в

кл е т к у

с о тр и ц а т е л ь н о й

ценой.

Э той

клеткой

я в л я е т с я

п е р в а я

к л е т к а т р еть его

столб ца ,

в которой цена

р а в н а

( — 2).

В о зн и к а е т

вопрос:

к а к

п рои зводи ть

п е р ем ёщ ен и е т о в а р а ?

Это

д е л а е т с я

по « кольцу »,

в к л ю ч а ю щ е м у

по кр ай н ей

м е ­

ре 4 клетки — одну свобод ную

с о т р и ц а т е л ь н о й

ценой

и

три

за н я т ы х

с

нулевой

ценой. Д л я

п ростей ш и х

сл у ч аев

это

« кольц о »

п р е д с т а в л я е т

собой за м к н у т ы й к в а д р а т .

В

т а б л и ц е

62 п о к а за н

к в а д р а т , од н а

ве р ш и н а которого

л е ­

ж и т

в

свободной

к л е т к е

с

о тр и ц ател ь н о й

ценой

( —2),

а

три

д р у ги е — в

к л е т к а х

с коли чеством т о в а р а . П о

этом у

к в а д р а т у

мы

и д о л ж н ы

п рои зводи ть

п ер ем ещ ен и е

т о в а ­

ра ,

но

то ль к о

так ,

чтобы

не н а р у ш а л и с ь

огр ан и ч ен и я

по

к о л и ч еств у

то в а р о в

на

с к л а д а х

и т р е б о в а н и я м

м а г а з и ­

нов.

В свобод ную

к л е т к у и

кл етку ,

л е ж а щ у ю

н а к р е с т

к

ней,

сл е д у е т д о б а в и т ь

н ек о то р о е коли чество

еди н и ц

т о в а р а

и

ту ж е

велич ину о тн ять

от

чисел в

д ву х

д р у ги х

клетках .

П р и

эти х у сл о ви ях

п е р е м е щ ат ь с я

по

« к о л ьц у »

м о ж ет

то л ь к о м еньш ее из

д ву х

чисел,

к о то р ы е

з а п и с а н ы

в

н а ­

к р ест

л е ж а щ и х

к л е т к а х

второй

пары , т.

е. пар ы ,

не

с о ­

д е р ж а щ е й

свободной

клетки . В

н аш ем

п р и м ер е

в к л е т ­

к а х второй

п а р ы з а п и с а н ы

числа 4 и 10.

М е н ь ш е е из этих

чисел

4

мы

м о ж е м п е р е м е щ ат ь

по

у к а з а н н о м у

вы ш е

Требуется

6

8

1 0

24

2

2

В ы числим

о б щ у ю

стоим ость

всех

п ер ев о зо к

по

новом у

плану .

В ы ч и слен и е ведем по

истинны м цен ам ,

т. е. по

цен ам

п ер ев о зк и

единицы

т о в а р а ,

известны м

из

т а б ­

лицы 60:

С = 6 -

1 + 4

• 3 +

8 • 1 + 6 - 4 =

6 + 1 2 +

8 + 24 =

50

руб.

П о ср ав н ен и ю

с исходны м этот п л а н

д а е т

8

руб. э к о н о ­

мии. Я в л я е т с я

л и

он н аи лу ч ш и м ?

В ы ясн и ть

это

м ож н о ,

п ри м ен яя

м ето д р а з р е ш а ю щ и х

сл а га е м ы х ,

к о то р ы е

п р о ­

с т ав л ен ы

в последней стр о ке

и последнем

с т о л б ц е

т а б ­

ли ц ы 63.

П о ясн и м

к р а т к о процесс н а х о ж д е н и я

этих

с л а га е м ы х .

В первом и вто р о м

с т о л б ц а х к л е тк и

с т о в а р о м

у ж е и м ею т

цены, р а в н ы е 0.

П е р в а я

к л е т к а

третьего сто лб ц а ,

в

которой

п р о с т а в л ен

то вар ,

им еет о т р и ц а т е л ь н у ю

цену

( — 2 ). Д л я

п р и в е д е н и я

этой цены

к н у л ю

по в тором у

с то лб ц у п р и б а в л я е м

к ц е ­

нам 2. П о сл е этого цена

во

второй к л етк е третьего

с т о л б ­

ца

с тан ет

р ав н о й

0 + 2 = 2, а

нам

н уж ен 0. С л ед о вател ьн о ,

по

второй

строке

н а д о

п р и б а в и т ь ( — 2 ).

Н о после этого

цен а во

второй

к л етк е

второго

с то лб ц а

с тан ет

равной

0 +

( — 2) =

— 2,

а

нам н у ж ен 0.

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

к

ценам

вто р о го

сто лб ц а следует

п р и б ави ть

2.

П р о д е л а в

все это,

переход им к со ставлен и ю

очередной т а б л и ц ы 64.

Таблица 64

М а г а з и н ы

И м е е т с я

С к л а д ы

2

3

н а с к л а д а х

( е д . )

1 .

0

2

0

1 0

------------------ ►

6

4

2

0

!

о

1 4

1

0

8

6

Требуется

6

8

1 0

2 4

Т а к

к а к

в

этой

т а б л и ц е

нет ни

одной

к л е т к и с

о т р и ц а ­

тельн ой

ценой,

то

д а л ь н е й ш е е с н и ж ен и е

стоим ости п е р е ­

в озок н е в о зм о ж н о и, с л ед о в атель н о ,

п л а н этой

т а б л и ц ы

н аи лу ч ш и й ( о п т и м а л ь н ы й ).

§ 2

СУЩЕСТВОВАНИЕ НЕСКОЛЬКИХ НАИЛУ.ЧШИХ

ПЛАНОВ

зы вается ,

если полученны й

н аи лу ч ш и й

п л ан

с о д е р ж и т

нуль хотя бы в одной клетке , в которой

не

п р о став л ен ы

единицы

т о в а р а ,

то во зм о ж н о

получ ить и д р у ги е н а и л у ч ­

шие

планы , с той ж е

общ ей

стоим остью

всех

перевозок .

Т а б л и ц а

64 с о д е р ж и т

цену,

р а в н у ю нулю , во второй к л е т ­

ке

первого

сто лб ц а , в

которой не

п р о став л ен о

к о л и ч е с т ­

во

т о в а р а .

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

б удут

су щ е с т в о в а ть и д р у ги е

н аи луч ш и е п л ан ы . П о к а ж е м , к а к их получить.

В т а б л и ц е

64 построим

« кольц о »

в вид е

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

верш ины

к о торого л е ж а т

в

к л е т к а х

с

нулевой

ценой. Е с ­

ли

по угл о вы м к л е т к а м

п ерем ести ть

6 единиц

т о в а р а ,

не

и зм е н яя

при этом коли чества т о в а р а

в

о стал ьн ы х к л е т ­

ках,

то

п олуч им

д ругой

н аи лу ч ш и й

план,

у к а з а н н ы й

в

т а б л и ц е

65.

Таблица 65

М а г а з и н ы

И м е е т с я

. С к л а д ы

2

3

на с к л а д а х

(ед.)

1

0

2

10

0

1 0

2

0

О

0

14

СО

6

Требуется

6

8

1 0

24

П о

это м у п л а н у

о б щ а я

стоим ость

всех п ер ев о зо к о с т а е т ­

ся

преж н ей . Д ей ств и тел ьн о ,

п р о и зв о д я

вы ч и сл ен и я

по

истинны м

ц е н ам

перевозки

еди ниц ы

т о в а р а ,

получим :

С = 6 - 2 +

8 - 1 +

1 0 - 3 = 1 2 + 8 +

30 = 50

руб.

Д л я

п о луч ения второго

н а и лу ч ш его

п л а н а

все 6 еди ниц