Файл: Сирл, С. Матричная алгебра в экономике.pdf

Пример. Стиглер [12] изучал задачу о рационе, в которой надо было минимизировать затраты при ограничениях на количество раз­ личных питательных веществ. Рассмотрим простейший случай. Пред­ положим, что некоторая диета состоит из белков и углеводов в коли­ чествах 70 и 150 граммов соответственно; далее, предположим, что

вналичии имеются только два продукта, один из которых стоит 0,2 цента за грамм и содержит 0,5 граммов белка и 0,2 граммов углеводов

врасчете на грамм; а второй

Задача (8) отличается от задачи (1) тем, что оба неравенства имеют знак «больше или равно», а также тем, что целевую функцию надо

ная с помощью неравенств этого вида (неравенства со знаком на графике (рис. 2) лежит выше прямых, заданных уравнениями, полученными из неравенств.

Область допустимых решений (заштрихованная) может быть рас­ ширена без ограничения, но так как мы минимизируем затраты, оп­ тимальное решение будет находиться ближе к началу координат.

Для получения графического решения вновь обратимся к «мето­ ду карандаша», выбрав на рис. 2 линии z = 60 и z = 45. Поскольку отыскивается минимум, то желательно смещаться вдоль линий убы­

231

вания целевой функции, т. е. в сторону начала координат. Продол­ жая движение карандаша, который все время остается параллельным

Минймальные затраты равны 32,54 центам, и они достигаются в до­ пустимой угловой точке.

Как и в задаче на максимизацию, оптимальное решение задачи на минимизацию всегда достигается в некоторой угловой точке области допустимых решений. На рис. 2 три допустимые угловые точки: (750; 0), (0; 3500) и (131,8; 206,1). Несложные преобразования дают возможность применить модифицированный симплекс-метод к реше­ нию задач на минимизацию этого типа.

6) ПЕРВОНАЧАЛЬНОЕ РЕШЕНИЕ ПРИ ОГРАНИЧЕНИЯХ ТИПА «БОЛЬШЕ ИЛИ РАВНО»

В случае ограничений типа «больше или равно» при записи их в форме равенства с помощью матрицы Л*, как это было сделано в фор­ мулировке (3), для снятия «нежесткости» дополнительные переменные необходимо ввести с отрицательными коэффициентами. Такие допол­

ние ограничения формулировки (9), нам нужно добавить к обеим частям равенства —20; таким образом, необходимо, чтобы коэффи­ циент при Xs 1 был отрицательным.

Задача (9) аналогична задаче (3), однако в случае минимизации матрица Л* не содержит в себе единичной матрицы, которая необхо­

на минимизацию начало координат обычно не является допустимым решением, однако для начала процедуры необходима единичная мат­ рица. Сейчас мы приступаем к ее созданию и последующему «устра­ нению».

Для получения начальной единичной матрицы в нашем примере (и вообще при ограничениях типа «больше или равно») мы следующим образом вводим искусственные переменные ха1 и xd2 в формулировку

(9):

минимизировать z = 0,2^ + 0,03х2

232

жем выполнить модифицированную симплекс-процедуру; однако точ­ ка, лежащая в начале координат, если начать с нее, не лежит в об­ ласти допустимых решений. Искусственные переменные названы так потому, что они недопустимы в окончательном решении, их необхо­ димо изъять в процессе решения. Если они равны нулю, то оставшие­ ся уравнения допускают лишь такие решения, которые лежат в области допустимых решений. Таким образом, мы можем с помощью искус­ ственных переменных начать с точки, лежащей в начале координат,

либо последовательным их изъятием, либо путем придания им таких цен (коэффициентов целевой функции), что они заведомо будут устра­ нены в процессе решения. Первую процедуру называют «Фаза-1», вто­ рую— «/И-метод». Обе процедуры выполняют одну и ту же задачу: они устраняют искусственные переменные прежде, чем будут пред­ приняты последующие шаги. «Фаза-1» описана у Хедли [91; мы опи­ шем «Л4-метод» в связи с его относительной простотой.

Если необходимо минимизировать затраты, то по «Л1-методу»* каждой из искусственных переменных назначается очень большой по­ ложительный коэффициент затрат (М ), в случае максимизации прибыли

Эта форма уже готова для процесса решения. Она имеет начальное решение, соответствующее единичной матрице, и гарантирует, что про­ цедура завершится в области допустимых решений в точке оптимума.

*Метод искусственного базиса. — Прим, перев.

233

3. НЕКОТОРЫЕ ОБОБЩЕНИЯ

а) СМЕШАННЫЕ ОГРАНИЧЕНИЯ

В параграфах 1 и 2 были рассмотрены такие задачи линейного прог­ раммирования, в которых ограничения относились либо все к типу «меньше или равно», либо все к типу «больше или равно». Для работы со смешанными ограничениями необходимо комбинировать процедуры, примененные выше, т. е., если ограничения записаны в форме не­ равенств, то следует включить дополнительные переменные с коэффи­ циентом -f 1 к левым частям неравенств типа «меньше чем ...» и избы­ точные переменные с коэффициентом —1 — к левым частям неравенств типа «больше чем ...». Затем в неравенства типа «больше чем ...» вво­ дят с коэффициентом -ф1 искусственные переменные, этим перемен­ ным соответствуют очень высокие коэффициенты затрат в целевой функции. Первоначальное решение содержит некоторые из дополни­ тельных переменных (которым соответствуют нулевые коэффициенты затрат) и некоторые из искусственных переменных (которым соответ­ ствуют очень высокие коэффициенты затрат). Применение модифицированого симплекс-метода начинается с исключения искусственных переменных.

б) ОГРАНИЧЕНИЯ В ФОРМЕ РАВЕНСТВ

В ограничения, которые с самого начала заданы в виде равенства, следует ввести искусственные переменные и применить «М-метод». При этом, хотя первоначальное решение будет включать в себя искусст­ венные переменные, модифицированный симплекс-метод в дальнейшем постепенно приравняет к нулю все искусственные переменные, обес­ печив тем самым выполнение равенств.

в) ПЕРЕМЕНА ЗНАКА В НЕРАВЕНСТВЕ

Для того чтобы можно было решать задачу с помощью модифици­ рованного симплекс-метода, необходимо, чтобы все элементы вектора b были неотрицательны. Если в первоначальйой формулировке зада­ чи некоторые из bt (i = 1 , ..., т) отрицательны, то соответствующие неравенства можно умножить на —1 , при этом меняются знаки тех элементов матрицы ограничений, которые соответствуют данному ог­ раничению, а также знак неравенства и знак соответствующего b (чего мы и добивались). Эта операция не меняет смысла ограничения и не оказывает никакого влияния на расположение области допусти­ мых решений. Например, ограничение типа «больше чем ...» при ум­ ножении на —1 переходит в тип «меньше чем ...», но при этом не меня­ ется ни сама задача, ни окончательное решение.

234

г) ЗАМЕНА ЗАДАЧИ ОПРЕДЕЛЕНИЯ МИНИМУМА НА ЗАДАЧУ ОПРЕДЕЛЕНИЯ МАКСИМУМА

I Большинство машинных программ приспособлено либо для реше­ ния задач на минимизацию, либо для решения’задач на максимизацию. Поэтому было бы полезно уметь переходить от одного типа задач к дру­ гому. Этого можно достичь просто, умножив целевую функцию на —1 и заменив слово «минимизировать» словом «максимизировать»; все остальное остается без изменения. Таким образом, минимизация

ется обратный переход от задачи на максимизацию к задаче на мини­ мизацию.

д) НЕОГРАНИЧЕННЫЕ ПЕРЕМЕННЫЕ

Мы описали процедуры линейного программирования для случая, когда все переменные неотрицательны. Однако эти процедуры приме­ нимы и для решения тех задач, в которых одна или несколько перемен­ ных могут быть отрицательными (т. е. эти переменные не ограничены). В формулировке задачи каждую из неограниченных переменных x-t заменяют выражением, содержащим пару новых переменных, xf — x f и далее решают заново сформулированную задачу, в которой фигурирует разность между двумя неотрицательными переменными xt — хТ, а не неограниченная переменная xt. После того как решение получено, в нем заменяют x f — x j на х{.

Пример. Рассмотрим задачу: минимизировать z = 2хг + Зх2 + х 3

и преобразуем ее таким образом, чтобы можно было применить моди­ фицированный симплекс-метод:

Максимизировать z = —2хг —Зх2—х+ + х~ + 0xSI + 0xS2 -f 0xS3—

— Mxdl— Mxdi— Mxda

235