Файл: Говар В.М. Математическое программирование учеб. пособие.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 29.06.2024

Просмотров: 143

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

 

 

 

 

-

43

-

 

 

 

Эти

значения

записываем

в

столбце fß

. Так как наименьшее

значение

Ѳ

равно

60, то ключевой будеі

являться строка,

содержа­

щая базисную

переменную х^.

Обозначим строку,

содержащую

перемен­

ную ï y ,

которая показывает,

что

х^ должна

из

базисных переменных

перейти

в

свободные.

 

 

 

 

 

На пересечении ключевых рядов с переменными х^ и Ху

находится

генеральный элемент, численное значение которого в данном случае равно четырем.

Выделим его каким-либо образом, например, обведем кружочком.

После этого переходим к составлению следующей симплексной таблицы,

соответствующей второму базисному решению. Согласно алгоритму, ее

заполнение начинаем с направляющей строки и первоначально эта таб­

лица

будет

иметь'вид

(табл.4.Ь)

 

 

 

 

 

 

 

 

 

 

Таблица 4.6

 

Базисные Свободные

 

i

 

1

(Столбец

 

перемен­

члены

 

x 4

 

Xy

контроль-

9 .

ные

 

 

 

 

 

 

1ных-сумм

Ч

 

[

 

 

 

i

 

 

ч

 

!

І

!

1

1

 

 

 

 

 

 

 

 

 

60

0,5[li25|

0,5j I

[ 0

J 0 0,25

63,5

 

L

( x j

 

 

i

 

' i

 

 

 

!

I

i

i

 

 

 

 

 

 

 

Стрелка при х^ показывает, что эта переменная только что .вве­

дена в

базисные

и строка,содержащая ее, является направляющей.

В ос -

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

столбца х^ мы должны накопить нули,

оперируя с

адв­

ентами

направляющей строки. Так, например, для получения нуля в этом

зтолбце

в строке

х^, умножим все элементы направляющей

строки

на

[~Ъ) и складываем с соответствующими элементами строки

предыду-

цей симплексной

таблицы (табл . 4 . 6) . Получим таблицу

(4.7)

 

~ 44 -

 

 

 

 

 

 

 

 

 

 

 

Таблица 4.7

 

Базисные

Свободные!

 

X

X

X IX

 

 

[Столбец

 

 

 

X

[Контроль- n

перемен­

члены

J - -

 

 

2

3

 

4

 

 

 

 

7

'ных сумм

ü

ные

 

 

 

 

1

 

 

 

 

 

5

6

 

 

 

 

 

 

Ч

120

1,5

0,25 0,5|

0

 

I

І 0

-0,75{

122,5

!

*

 

1

П

»

 

 

Т

 

 

•

!

 

1

-5

 

 

 

t

 

 

!

 

 

 

i

 

 

 

 

 

 

і

 

 

 

 

 

 

 

 

 

 

 

 

—ъ

60

 

1г

0,5

I

 

0 j

0

 

{

 

î

 

ч

0,5

1,25

 

,0,25;

63,5

{

L ( I )

 

 

 

 

 

 

 

Ii

 

 

 

Ï

 

 

 

 

 

 

 

 

Î

 

1

 

 

1

 

i

 

 

 

 

 

 

 

 

 

 

 

 

60°(-3)+300=I20;

0,K(-3)+3=I,5;

 

1,25* (-3)+4=0,25;

0,5*(-3)+2 «0,5;

Г(-3)+3

sO ;

 

 

0'(-3)+I=I ;

 

'63»5*(-3)+3I3=Ï22,5

 

 

 

 

 

 

 

0*(-3)+0-0 .

1

 

Находим сумму

свободного

члена

и всех

 

коэффициентов

при перемен­

ных строки X-

120*1,5+0,25+0,5+0+1+0-0,75=122,5 Полученная сумма равна числу, вычисленному в столбце контроль­

ных сумм, следовательно,

все элементы строки х^ вычислены правильно

и записаны в таблице (4.7)

 

Для исключения нулей s остальных клетках столбца х^ умножаем

направляющую строку последовательно на (-2)

и на 12 и суммируем ре ­

зультаты соответственно

с элементами с троки xf e и L ( X ) первоначаль­

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

таблицы

(табл.4.5). Второе

базисное решение помещено.

в таблице (4.8).

 

 

 

Анализируем

полученное второе базисное

решение. Ь индексной

строке имеются два отрицательных числа (-3)

и (-2), поэтому план не

является оптимальным. Решение необходимо продолжать по изложенному выше алгоритму. Симплексные таблицы (4.Ь) и (4.8) записывались от­ дельно в целях большей наглядности. При практических вычислениях асе симплексные таблицы записываются в одну общую таблицу, строки

ксЕорой добавляются для получения оптимального решения. Полное реше-

- 45 -

 

ние приводится в сводной таблице

(4.9)

Таблица 4.8

- —

 

 

 

 

j—г-.—j

 

Базис- іСвооод-t

i

x

ные'ne-!ные

j

x

ремен-

j

члены

1

-

^

ные

 

 

І , 5 |

 

х 5

 

1

120

 

0,25

х 6

 

j

90

j

OJ

1,5

Х 4 '

 

j

60

J

0,5}

1,25

L

( X)j

720

1

- 3|

10

I

 

1

 

...

 

!

 

 

 

t

 

Y

 

 

S \ X 4

 

х б !

x 7

 

X 5

 

 

1

 

 

 

1

 

 

 

j

I

 

1

 

0,5j

0

0

!

-0,75

j

2

0

j

0

j l

j*-0,5

0,5

I

 

 

т

 

0,25

 

0

[0

 

 

 

 

 

 

 

-

2

0

 

0

jo

 

3

CKC Э

І 122,5І

j 94 j

63,5

728

В ІУ таблице табл.(4.9) в индексной строке все коэффициенты

неотрицательны, следовательно, четвертое базисное решение является

оптимальным. По оптимальному плану

Xj =

65, x-j = 45,

х^ ="5

при

этом' L

( X ) = 1005.. Это означает, что

предприятие

должно

выпус­

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

65 изде,лий-вида

bji

45

изделий •

вида

и 5 изделий-яида В^; при этом максимальная прибыль

от реа­

лизации

продукции будет

составлять

ІСО5 денежных единиц.

Дальней­

ший анализ показывает,

что х 2 , х^,

х^ и Ху являются

свободными пе­

ременными, следовательно, их численное значение ра±>но нулю. Эконо­

мически

это означает, что при оптимальном плане

выпуск

изделий

вида В 2

является неэффективным,

а сырьевые

ресурсы

Aj

,А2 и

предприятием использованы полностью.

 

 

 

 

При-решении задач в симплексных таблицах возможны следующие

упрощения при вычислении:

 

 

 

 

 

а)

если^з -ключевой строке исходной симплексной таблицы имеют­

ся нули,

то столбцы,

содержащие

их* а последующую

симплексную таб­

лицу переписываются

без изменения;

,

..

'

 

 

 

 

 

 

 

 

-

46 -

 

 

 

 

 

 

 

 

 

 

 

 

 

б)

если в ключевом

столбце

исходной

симплексной

таблицы,

 

имеются нули, то строки, содержащие их;

В последующую

симплекс­

 

ную таблицу

также

переписываются без

изменения.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таблица

4.9

 

 

Базисные

 

Свобод-t

 

{

 

 

 

 

 

 

 

 

 

 

 

 

1

g

 

 

 

 

 

 

 

 

 

 

 

 

 

 

CKC|

 

переменные

ные

i

x

L x

 

 

 

X 4

j 4

JX6

| X 7

 

І

 

 

члены

 

|

|

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3C0

 

3

j

4

j

2

 

3

;

I

j

о

;

0

r 3 D

'

100!

Ч

 

!

210

!

I

 

U

 

3

•

2

 

0

І

I

j

0 .

221

 

105

таб.

 

 

 

 

 

 

 

 

 

 

©

 

о

j

о

!

i

254

 

60

•

 

 

 

240

 

2

it

5

 

2

 

 

 

 

 

 

 

 

 

 

 

 

L

С *

}

0

 

-9

 

-5

 

-8

 

-I2T

0

j

0

J

0

-34

 

-

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

120

 

^ Ц ) J0,25 0,5.

J 0

 

І

І

0

1-0,75

I22.5J

80

 

<•

 

j

90

JO

| і , 5 -

2

j 0

J O !

I

i-0,5

94

 

_

 

х 6

 

 

 

П

х 5

 

г

 

i

l

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

j

I

.!

0

j

0

j

0,25

63,5

120

таб.

х р

 

j

60

JO,5 - I.25J0.5

L

( X )j

720

i-3

 

10

|-2

[ 0

!

0

j

Ö ! 3

72Й

 

-

 

x f -

 

j

80

 

I

 

I

 

 

 

 

F F

 

. o l - i .

8lf_

 

240

 

x 6 —

 

j

90

 

0

 

 

 

 

 

 

 

I

t-

I

94

 

45

 

 

 

 

4

-

(2)

!

о

j

о

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2~

 

 

 

ТО f\

Хц.

 

j

20

 

0

 

i - f

+

 

h

 

J

, .

о

 

I

22^-

60

L

С x

)

960

 

0

 

 

 

T

 

 

 

~2~

 

 

 

 

 

 

 

 

-I f

1

0

 

2

 

0

I - f

973

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x ï

 

 

65

 

I

 

 

 

 

 

 

 

 

-

I _

-

5

66

 

 

 

 

 

 

 

 

 

 

 

•

 

<

 

 

 

 

6

 

Т Г

 

 

 

 

x7~*

 

\

4-5

{. 0

 

 

 

i

І

о

 

û

 

JE.

-+

47

 

 

-ІУ

5

 

 

 

 

 

 

 

 

 

[

 

 

 

 

2

 

 

 

(таб.

x 4

 

!

5

 

 

 

 

 

о

!

i

 

 

 

 

 

7

7

 

 

f

 

 

 

 

 

0

i

 

*

 

1

 

 

 

 

 

12

 

 

 

t

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i

L e

x

;

1005

 

0

j l *

0

1

0

 

 

 

 

4

 

1020

 

r

 

j

 

 

H

 

 

!

 

 

 

 

 

 

1

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f

- 47 -

йИКЩЕНИЕ, ЗАЦИКЛИВАНИЕ И ИХ ПРВДОЛЕНИЕ В ЗАДАЧАХ, РЕШАЕМЬК СИМПЛЕКСНЫМ МЕТОДОМ.

Иногда при решении задач линейного программирования можно

встретиться с так называемым вырождением, которое наступает в

том случае, если в опорном плане одно или несколько значений ба­

зисных переменных равны нулю. При этом число положительных базис­

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

уравнений-ограничений

исследуемой

задачи.

 

 

Вырождение может наступить и при переходе

от одной симплекс­

ной таблицы к другой. При этом в анализируемой

симплексной табли­

це должно быть несколько, не менее двух,

наименьших одинаковых

значений ©

• Б этих случаях генеральный

элемент может быть выбран

неоднозначно и, следовательно, в процессе решения может произойти

зацикливание. При зацикливании

одни и теже

опорные

планы повторя­

ются периодически и оптимальное

решение может быть не получено.

Возможность преодоления этого затруднения рассмотрим на сле­

дующем

примере.

 

 

 

 

 

 

 

 

 

Найти (4.19)

|_,

( X ) = 2Xj + х 2

+ Зх3 + х 4

+ гх^-гт^х

.

при следующих

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

 

 

 

 

 

 

2Xj

 

 

+ 2 х 3

+ 2х^

4.

ІЬ,

 

 

(4.20)

 

* З х

2

 

+3х3

+ Зх^ +3х5

^

24,

 

 

 

Х І +

2 х 2

+

*3

 

+ х 5

 

I Z f *

 

 

(4.21)

х^

s

0,

где j ,

= 1,2,3,4,5.

 

 

 

 

После перехода

от системы

ограничений-неравенств (^.20>

к

системе уравнений-ограничений, запоняем симплексную таблицу (4.10) первым базисным решением.*

В первом опорном решении в двух первых строках с базисными

переменными х ь

и Ху

получаем два наименьшие одинаковые симплекс­

ные отношения

0 =

8 .

Смотрите также файлы