§ 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.Для большей наглядности они обведены пунктиром. Первая симплекс-таблица — без строки для/ — выглядит так:
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 (точка означает скалярное умножение),
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).
Рекомендуем читателю самостоятельно довести решение примера до конца, сопровождая каждый шаг контролем строки/.
Обсуждение Математика в экономике
Комментарии, рецензии и отзывы