Имя материала: Математика в экономике

Автор: Солодовников А.С.

§ 8.3. работа с целевой функцией

 

При подготовке задачи линейного программирования к решению с помощью симплекс-метода приходится решать технический вопрос. Как наиболее рационально находить выражение целевой функции/через свободные неизвестные?

Пусть задача имеет вид:

х{ =а4х4 + а5х5 + а, ■ х2 = Р4х4 + p5x5 + В, (8-21) х3 = у4х4 + у5х5 + у,

 

дг.-^О (i= 1     5),

/= с0 + cjjcj + с2х2 + c3x3 + с4х4 + с$х5 -> min. (8.22)

Чтобы получить требуемое выражение для/, следует в равенстве (8.22) заменить xltx2,х3 в системе (8.21). Осуществляя такую замену, находим:

/= с0 + с, (а4 х4 + а5х5 + а) + с2 ф4 х4 + В5 х5 + В) + + с3 (у4 х4 + у5 х5 + у) + с4 х4 + с5х5.

После приведения подобных членов получим:

/ = 64х4 + 65jc5 + 5,

где, очевидно,

5 = с0 + С| а + с2 Р + с3 у, 64 = с, а4 + с2 Р4 + съу4 + с4, 55 = с, а5 + с2 Р5 + с3у5 + г5.

Обозначим:

сб~ (ci> с2> сз)—вектор из «базисных» коэффициентов в равенстве (8.22), h = (а, р, у) — вектор свободных членов в системе (8.21), ^4 = (а4> ?4> Y4) — вектор из коэффициентов при х4 в системе (8.21), Л5 = (а5, р5, у5) — вектор из коэффициентов при х5 в системе (8.21).

Тогда предыдущие равенства перепишутся в виде

0 =   + ( ся>п ) (скалярное произведение),

84 = (^,Л4) + г4,

 

Чтобы научиться правильно использовать эти формулы, запишем их так: S =(cE,h) + c0,

 

- 85 = ( fff. - А5 ) - г5-

и далее учтем, что h — это столбец свободных членов из симплекс-таблицы, отвечающей (8.21), -А4 — столбец для неизвестного х4 из

той же симплекс-таблицы, а -Л5 — аналогичный столбец для х5.

Обозначим эти столбцы Л , А4 и h5 . Тогда получим:

imf>   mad mad

 

^<сБ,И4)-с4, (8-23)

тав 'Ш*в

55 =(ёд, Л5)-с5.

шиЛ /гиб

Это и есть искомые формулы.

Обычно поступают так; над неизвестными х, .... jc5 в заглавной строке симплекс-таблицы пишут числа с, с5 (коэффициенты из равенства (8.22)), а слева от базисных неизвестных пишут С|, Cj, с3 («базисные» коэффициенты из равенства (8.22)). Далее пользуются формулами (8.23) для заполнения последней строки таблицы (строки для J).

Разумеется, при переходе от первой симплекс-таблицы ко второй строка для/получается сама собой (при помощи симплекс-алгоритма, описанного в конце § 8.2 — см. пункт 5 алгоритма). Но в принципе ее можно получить также и с помощью формул (8.23). Такой «двойной» способ нахождения последней строки можно использовать в качестве контроля вычислений.

= 1, = 4, = 5,

 

Пример. Решим задачу

+ 2х,

ХЪ

- х4 + х5 + -2х4+ х5

Зх| - 5х2 + -2*|+ 2х2 -Х| + 3*2

min.

 

х,.>0 (i = 1.....7),

/= 9 + Зх| + 5х2 - Зх4.+ 2х5 - х7 ■

Здесь исходный базис образован неизвестными х3 х6 х7.Для большей наглядности они обведены пунктиром. Первая симплекс-таблица — без строки для/ — выглядит так:

 

 

 

9

3

5

0

-3

2

0

-1

 

Базисные неизвестные

Свободные члены

х

Х2

х4

Х5

х6

*7

0

1

3

-5

1

2

0

0

0

0

4

-2

2

0

- 1

1

1

0

-1

х1

5

- 1

3

О

-2

1

0

1

 

/

 

 

 

 

 

 

 

 

Для заполнения последней строки таблицы можно воспользоваться формулами типа (8.23):

- 3 = -2 (точка означает скалярное умножение),

Подпись: (0
4
5 =

maf>

 

+ 9 = 4.

Итак, дана задача:

аххх + а2*2 + аЗхъ + а4х4 + aSx5 + а ~ О' б,*, + Ь2Х2 + />з*3 + b4x4 + 65*5 + Ъ ~ °> (8.24) с,лг, + CjXj + с3х3 + с4х4 + csx5 + с = О,

jc,>0 (/=1,2,3,4,5), (8.25)

/= dxxx + d2x2 + л3х3 + rf4x4 + ^5*5 + d "* min- (8.26)

Свободные члены a, b, с уравнений будем считать неотрицательными: если это условие не выполняется, например, если а < 0, то, умножив обе части первого уравнения на -1, получим уравнение, в котором свободный член больше 0. Итак, пусть

(8.27)

а>0, Ь>0, с>0.

Дальнейшая работа с таблицей осуществляется в соответствии с симплекс-алгоритмом. При этом для контроля правильности вычислений можно использовать формулы типа (8.23).

Рекомендуем читателю самостоятельно довести решение примера до конца, сопровождая каждый шаг контролем строки/.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 |