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

Т а к и м о б р а з о м ,

к а ж д у ю

за д а ч у ,

в которой

огран и ч ен и я

не с о д е р ж а т

н еоб ходи м ы х

нам неизвестны х ,

п ри ходи тся

р а с ш и р я т ь з а

счет введен ия

искусственны х неизвестны х .

Б езу сл о в н о ,

р а с ш и р е н н а я

з а д а ч а

сущ ественно

о т л и ч а е т ­

ся от исходной .

Но, н есм отря н а

это,

мы

в ы н у ж д е н ы

д е ­

л а т ь п ер е х о д

к р асш и р ен н о й

за д ач е , т а к

к а к

она м о ж е т

б ы ть р е ш е н а

известны м

нам

си м п лек сн ы м м етодом .

В о зн и к а е т вопрос:

к а к

получить

реш ение

исходной

з а д а ­

чи,

если

р е ш а т ь

вм есто

нее р а с ш и р е н н у ю

з а д а ч у ?

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

при м ен ение

си м п лек сн ого

м е то д а

к

р а с ­

ш иренной з а д а ч е

п о зв о л я е т

построить

план ,

в

котором

к а ж д а я

из

искусственн ы х

неи звестны х

р а в н а

нулю .

Н о

та к о й п л а н

будет

я в л я т ь с я

и п л а н о м

исходной

з а д а ч и ,

т а к

к а к если

все и скусственн ы е неизвестны е

р ав н ы

нулю ,

то

ф у н к ц и я

цели

и огран и ч ен и я

р асш и ренной

з а д а ч и

о б ­

р а щ а ю т с я

в

исходны е.

Д а л ь н е й ш е е

у л у ч ш ен и е

п л а н а

п р о и зв о д и тся

при

пом ощ и

обы чного

с и м п л ек сн о го

п р о ­

цесса.

Р а с с м о т р и м

реш ен ие с ф о р м у л и р о в а н н ы х

вы ш е

д в у х

з а ­

дач .

Задача 1. Н а й т и

н а и б о л ь ш е е зн ач ен и е ф ункц ии

С — Х \ - р 2 х 2 - р 3 * з — *4— Л І Х д — A l X ß

при вы п о л н ен и и условий

* і + 2x2 + 3*з

-Р*5

= 1 5

2*і + Хз + б^з

+ х6 = 20

* і -Р2*2-Р

*з+*4

=10.

В к а ч е с тв е исходного п л а н а

возьм ем :

*і =

0; *2 = 0; *з = 0;

* 5= 15; * 6= 20; * 7= 1 0 .

П ри с о с та в л е н и и

первой

с и м п л ек сн о й

т а б л и ц ы

н е о б х о д и ­

мо

цены

б р а т ь

с

п р о т и в о п о л о ж н ы м и

з н а к а м и ,

т а к

к а к в

д а н н о м

с л у ч а е

р е ш а е т с я

з а д а ч а

на м а к с и м у м

( т а б л .

31).

П о с л е д н я я

с т р о к а

этой

т а б л и ц ы р а з д е л е н а н а

д в е части

по причине,

к о т о р а я сейчас

с тан ет пон ятной .

У м н о ж а я

эл е м е н т ы с т о л б ц а

цен

на

с о о тв етств у ю щ и е

эл ем ен ты

п л а н а , получим

С к л а д ы в а я ,

к а к

р а н ь ш е ,

эти ч и сл а , н а й д е м число, к о т о ­

рое мы р а н ь ш е

п и с ал и

в п о сл ед н ю ю

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

« П л ан » . Э то число р а в н о

10+35Л1.

О но состоит

и з

д в у х с л а га е м ы х :

первое,

н е за в и с я щ е е от

М , р а в н о 10

и второе, з а в и с я щ е е

от М, р а в н о 35Л 1

В п о след ню ю

с троку п л а н а

за п и с ы в а е м теп ерь

д в а

ч и с ­

л а : 10 и

35, т.

е. с л а гаем о е ,

не з а в и с я щ е е от М,

и

к о э ф ­

ф ици ент

сл а га е м о го , з а в и с я щ е г о от М.

Точно т а к ж е

прои зводи м р а зд е л е н и е р е зу л ь т а т о в

и

д л я

всех о с т а л ь н ы х столбцов.

Д л я с т о л б ц а Х\ находим :

и,

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

послед н ю ю с троку

этого с т о л б ц а з а ­

п и сы в аем д в а числа:

2 и 3.

Т а к к а к д л я с т о л б ц а Хг

М •2= 2М

+ М • \=М

1 - 2 = 2

2

+ 3 v W - ( - 2 ) = 4 + 3M,

то

в п о сл ед н ю ю стр о к у этого с т о л б ц а

за п и с ы в а е м ч и сла

4

и 3.

Д л я с т о л б ц а х3 наход им

и

п о это м у

в

послед н ю ю

его

с т р о к у за п и с ы в а е м

ч и с л а

4

и 8. Л е г

к о

провери ть ,

что

д л я сто лб ц о в х4, xs

и Хб в

1-

1=

0.

С о стави в

первую

си м п лек сн ую

та б л и ц у ,

переходим к

у лучш ени ю

п л а н а .

Д л я

этого

р а с с м а т р и в а е м

с н а ч а л а

второй

р я д

чисел

последней

строки и

среди

них о т ы ск и ­

в а е м н аи б о л ь ш е е

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

число.

В

н аш ем

п р и ­

м ер е

этим

числом

я в л я е т с я

8,

кото р о е п р и н а д л е ж и т

с то лб ц у неи звестной

х3.

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

это т столб ец я в ­

л я е т с я ге н е р а л ь н ы м .

Д л я

н а х о ж д е н и я

генеральной

строки ,

к а к и

р ан ьш е ,

с о с та в л я е м

о тн ош ен и я

элем ентов

п л а н а

к

соответствую щ и м

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

эл е м е н т а м

ге н е р а л ь н о го сто лб ц а :

1 5 : 3 =

5;

2 0 : 5 = 4;

10:

1 =

10.

К а к

видно,

н а и м е н ь ш е е

из

эти х

чисел

4

соответствует

второй

строке,

и,

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

он а

и я в л я е т с я

ген е ­

р а л ь н о й ,

а

число

5 —

ге н е р а л ь н ы м

эл ем ен то м . Н а

место

неи звестной х& н а д о

ввести в п л а н

неи звестн ую

х3.

В о второй

с и м п л ек сн о й

т а б л и ц е

п р е ж д е

всего

вы чи сляем

эл ем ен ты

той

строки ,

к о т о р а я

стоит

на

м есте

г е н е р а л ь ­

ной.

П р и

этом

м о ж н о

не в ы ч и сл ять

элем ен т ,

п р и н а д л е ­

ж а щ и й

с то лб ц у иск усственн ой

неи звестн ой , вы веден ной

из п л ан а .

Эти

э л е м е н т ы вы ч и сл яю тся , к а к

обычно,

д е л е ­

нием

эл е м е н то в ген е р а л ь н о й

строки на

ге н е р а л ь н ы й э л е ­

м ен т

( т а б л . 32).