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

§ 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.Для большей наглядности они обведены пунктиром. Первая симплекс-таблица — без строки для/ — выглядит так:

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

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

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).

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