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

И з т а б л и ц ы

60

видно,

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

т о в а р а

т р е ­

буется д л я

к а ж д о г о

м а г а з и н а

и скольк о

единиц

т о в а р а

им еется

на

с к л а д а х .

О б щ е е

коли чество

т о в а р а ,

т р е б у ю ­

щ ееся м а г а зи н а м ,

равн о

коли честву т о в а р а ,

и м ею щ ем у ся

на

с к л а д а х .

Э то условие д о л ж н о

в сегда

с о б л ю д а т ь с я при

при м ен ении

р а с п р е д ел и те л ь н о го

м етода.

В у г л а х

к л е т о к

т а б л и ц ы

60 п р о став л ен ы

цены

перевозки

единицы

т о в а р а из к а ж д о г о

с к л а д а

в

к а ж д ы й

м агази н .

Т ак , н ап р и м ер ,

цены

перевозк и

единицы

т о в а р а

из

п е р ­

вого

с к л а д а

в к а ж д ы й

из

м а га зи н о в

р авн ы

с о о тв етс тв е н ­

но

1,

2 и 3 руб.

Теперь, к о гд а д а н н ы е р а с п о л о ж е н ы в виде т а б л и ц ы ,

над о

най ти н ек оторы й

отп равн ой

в а р и а н т реш ен ия

з а д а ч и с

тем ,

чтобы потом у лучш и ть его.

Д л я

о т ы ск а н и я

первого

р еш ен ия су щ ествует о п р е д е л е н ­

ное

пр ави ло ,

н а зы в а е м о е

п р а в и л о м

« севе р о -за п а д н о го

угла» . П р и м е н и м

это п р а в и ло в н аш ей зад ач е .

1. Н а ч и н а е м

с

« сев ер о -зап ад н о го » ,

или

и н аче

верхнего

левого , у гл а

т а б л и ц ы ,

с р а в н и в а е м итог

н ал и ч и я

по

с т р о ­

ке

10 с итогом т р е б о в а н и я

вн и зу с т о л б ц а 6.

2.

М ен ьш ее

из

эти х чисел

6

п о м е щ а е м

в верхню ю левую

кл е т к у т а б л и ц ы ,

т.

е.

т р е б о в а н и е

первого

м а г а з и н а

« у д о в л е т в о р я е м »

з а

счет

первого с к л а д а . Ч и с л о

6 в ы ч и ­

таем

из

и м ею щ его ся

на

первом

с к л а д е

к о л и ч еств а

е д и ­

ниц

т о в а р а

10,

остается

4 своб од н ы х

единицы

т о в а р а .

3. С м о тр и м

вп р аво ,

на

сл ед у ю щ и й

столбец , у с т а н а в л и ­

ваем

кол и ч ество

единиц

т о в а р а , н еоб ходи м ое

вт о р о м у

м а га зи н у ,

оно р а в н о

8.

С р а в н и в а е м эту

в елич ину с и м е ю ­

щ и м ся в

н а л и ч и и

коли чеством

еди н и ц

т о в а р а

4

н а п е р ­

вом склад е .

4.

М е н ь ш е е

из

эти х д ву х

чисел

4 п р о с т а в л я е м

во второй

к летке первой

строки ,

т.

е.

из

п ервого

с к л а д а

« за в о зи м »

во

второй

м а г а з и н 4

единицы

т о в а р а .

Т еперь

весь

т о в а р

первого

с к л а д а

о к а з ы в а е т с я

« р асп р ед ел ен н ы м » ,

и м о ж н о

15*

227

переход ить

к

« расп р ед ел ен и ю »

т о в а р а - в т о р о г о

с к л а д а .

5. Во

второй

м а г а зи н

тр ебуется

8

еди ниц

т о в а р а ,

а

мы

« за в е зл и » пока из п ервого

с к л а д а

то ль к о

4

единицы .

Н е ­

д о ст а ю щ и е

4

единицы

над о

« завезти »

из

второго

с к л а д а .

В ы ч тя эти

4

единицы

из

14 единиц ,

и м ею щ и х ся

на

в т о ­

ром склад е , получим

10 единиц,

ко то р ы е п о д л е ж а т

д а л ь ­

ней ш ем у р асп ред елен и ю .

6. П ер ех о д и м

к тр е ть е м у

столбцу .

О с т а в ш и е с я

10

единиц

т о в а р а второго с к л а д а « заво зи м »

в трети й м а га зи н ,

к о ­

то р о м у к а к р а з и тр еб у ется это количество .

И сходн ы й

в а р и а н т перевозок п р е д с та в л е н

в т а б л и ц е

61.

Таблица 61

М а г а з и н ы

И м е е т ­

ся на

С к л а д ы

2

3

с к л а д а х

(ед .)

1

1

4

2

3

1 0

6

2

2

4

1

4

14

+ 1

1 0

Требуется

6

8

1 0

24

-

1

- 2

-

5

Д л я

уверенности

в п р ав и ль н о сти

р е зу л ь т а т о в

п олезн о

с у м м и р о в а т ь

все

п р о с та в л ен н ы е

вели ч и н ы

по г о р и зо н т а ­

ли и

вер ти кал и .

Э то

д а е т

в о зм о ж н о с ть проверить:

у д о в ­

везен ы

т о в а р ы из

с к л а д о в .

П о с л е того,

к а к

исходны й в а ­

р и а н т п еревозок

составлен ,

с л ед у ет прои звести оценку

о б щ ей

стоим ости

всех этих

перевозок .

О н а

по л у ч ается в

р е зу л ь т ат е у м н о ж ен и я

коли честв перевози м ы х то в а р о в

на соответствую щ ую цену п ер ево зк и единицы

т о в а р а и

с л о ж е н и я полученны х р езу л ь тато в :

С = 6*1 + 4 - 2

+ 4-1 +

10 4 = 6 + 8 + 4 + 40 = 58

руб.

П о сл е о п р е д е л ен

и я исходного в а р и а н т а п еревозок н а ч и ­

не всегда.

Д е л о

в том, , что

число

зап о л н ен н ы х к л е т о к

в

исходном

в а р и а н т е

д о л ж н о

бы ть

вполне

о п ред елен н ы м

д л я того,

ч тоб ы

бы л при м ен им весь д ал ь н е й ш и й

процесс

у лучш ен и я , а им енно — это

число

д о л ж н о б ы ть

на е д и ­

ницу м ен ьш е сум м ы

числа строк и числа столб ц ов н аш ей

таб л и ц ы .

В т а б л и ц е

2

число

стр о к

р ав н о

2 (2 с к л а д а ) ,

а

число сто лб ц о в

р а в н о

3

(3 м а г а з и н а ) ,

их

с у м м а

р а в н а

5.

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

число

за п о л н е н н ы х

то в а р о в

кл ето к

д о л ж н о р а в н я т ь с я 5 — 1 = 4.

Р а с с м а т р и в а я т а б л и ц у

61, видим ,

что

она

у д о в л е т в о р я е т

этом у тр е б о в а н и ю ,

и

п оэтом у м о ж н о

переход ить

к у л у ч ­

ется при по м о щ и

р а з р е ш а ю щ и х

с л а га е м ы х , или,

д р у ги ­

ми с л о в ам и ,

при

пом ощ и

н улевой ко р р ек ти р о вки .

С у щ ­

ность этого

м е то д а

состоит в том , что к

цен ам п ер е в о зо к

единицы

т о в а р а по

с тр о к ам и с т о л б ц а м

т а б л и ц ы

п р и б а в ­

л я ю т с я

т а к и е

с л а га е м ы е ,

чтоб ы

з тех

кл етк ах ,

где

п р о ­

с т ав л ен ы ед и н и ц ы

т о в а р а ,

цены

с т ал и р ав н ы м и

нулю .

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

первы й

сто лб ец т а б л и ц ы

61,

у словн о

с о о т ­

ветству ю щ и й

п ер во м у

м а га зи н у ,

видим ,

что

в нем

з а п о л ­

нена л и ш ь п е р в а я

кл етка ,

в

которой

стоит

число

6.

С л е ­

д о в ат е л ь н о ,

цену

1

в

этой

к л е т к е н а д о

привести

к нулю .

Д л я этого к

ц е н ам

первого

с т о л б ц а

п р и б а в л я е м

( — 1),

к о т о р а я

у к а з а н а

в

последней

с т р о к е

этого

ст о л б ц а .

П о с ­

1+

( — 1) =

0,

а во второй

2 +

( — 1) = 1-

Р а с с м о тр и м

второй

столб ец т а б л и ц ы

61,

соо тветству ю ­

щ ий

в тором у

м агази н у . В

этом

с то лб ц е

зап о л н е н ы

обе

клетки ,

в

к о торы х

сто ят

числа

4

и 4.

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

обеи х этих к л е т к а х цены надо п ри води ть к нулям .

С н а ч а л а при ведем к нулю

цену 2

первой

(верхней ) к л е т ­

ки сто лб ц а .

Д л я

этого

к

ценам

второго

с т о л б ц а п р и б а ­

вим

( — 2).

Ц е н а

в первой

клетке

ст ан е т

р а в н о й

нулю , а

ц ен а во второй к л етк е составит:

1+ ( — 2) = 1— 2 = — 1.

Н о н а м

нуж ен

нуль

и

во

второй

клетке ,

т а к к а к в

ней

т а к ж е

п р о ставл ен о

число

то в а р а .

Ч т о б ы

« погасить »

п о ­

лучен ную

( — 1),

п р и б а в и м

к ценам по

второй строке 1.

В р е зу л ь т а т е в у к а за н н о й клетке будем

им еть:

(

-

1) + 1= 0.

О с т а е т с я

р а с с м о тр е т ь

вторую к л е т к у

т р еть его

столб ца ,

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

Т а к к а к по второй стр о ке

мы у ж е

п р и б а в и л и

к цен ам

1,

то в

этой

к л е т к е

цен а о к а зы в а е т с я

р а в н о й

4 + 1 = 5 .

Ч то б ы

привести

ее к

нулю ,

надо

к ц е н ам

третьего с т о л б ­

ца п р и б а в и т ь (— 5.

О п р е д е л и в

все

р а з р е ш а ю щ и е с л а га е м ы е

и

п р о с т а в и в их

в т а б л и ц е

61,

переход им

к

со ставл ен и ю с л ед у ю щ ей

т а б ­

л и ц ы

(табл . 62)

с т а к и м

ж е к оли чеством

ст р о к

и с т о л б ­

цов,

к а к и в т а б л и ц е

61.

Таблица 62

М а г а з и н ы

И м е е т с я

С к л а д ы

1

на с к л а д а х

2

3

(ед.)

1

0

0

- 2

10

6 ..........

4

—1

2

1 ...........2

I

1

«

14

° - 2

..... 1

А<---------

10

Требуется

6

8

10

24

2

2

Н о в а я цен а в

к а ж д о й

к л етк е

этой

т а б л и ц ы

п о л у ч ается в

р е зу л ь т ат е п р и б а в л е н и я

к стар о й

цене

той

ж е

кл етки

р а зр е ш а ю щ и х

с л а га е м ы х

по ст о л б ц у и строке,

в которы х

р а с п о л о ж е н а

к л етк а .

Ясно,

что

в

кл е т к а х ,

где

р а н ь ш е

бы ли то в а р ы ,

цены д о л ж н ы

о к а з а т ь с я

р ав н ы м и

нулю .

П р о вер и м цены в д ву х сво б о д н ы х к летках .

Д л я

второй к л е тк и первого с т о л б ц а имеем :

с т а р а я

цена

2

+

р а з р е ш а ю щ е е с л а га е м о е по столб ц у

( — 1)

р а з р е ш а ю щ е е

с л а га е м о е по строке

1

н о в ая цена

2.

Д л я

первой

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

с т о л б ц а а н ал о ги ч н о

н а х о ­

дим:

с т а р а я

цен а

3

+

р а з р е ш а ю щ е е

с л а га е м о е

по столб ц у

( — 5)

р а з р е ш а ю щ е е

с л а га е м о е

по строке

0 (нет

его)

н о в ая цена

( —2 ).