Файл: Егоров, Казаков Мет. по лин. програм..pdf

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНДУСТРИАЛЬНЫЙ УНИВЕРСИТЕТ

О.П. Егоров О.Л. Казаков

Линейная алгебра и математическое программирование для экономистов

Часть 2. Математическое программирование

УЧЕБНОЕ ПОСОБИЕ

Москва 2004

2

Содержание

Предисловие 1. Линейное программирование

1.1.Задача линейного программирования

1.1.1.Задача об ассортименте продукции

1.1.2.Задача составления смеси (о диете)

1.1.3.Задача о раскрое

1.1.4.Задача о сменно-суточном планировании работы

1.2.Области решений задачи линейного программирования

Вопросы для самопроверки

1.3.Графическое решение задачи линейного программирования

Вопросы для самопроверки

Задания для самостоятельной работы

1.4.Анализ оптимального решения на чувствительность к изменениям исходных условий

1.4.1.Улучшение оптимального решения за счет изменения дефицитного

ограничения

1.4.2.Изменение недефицитного ограничения без изменения оптимального решения

1.4.3.Степень чувствительности оптимального решения к изменениям дефицитных ограничений

1.4.4.Пределы изменения коэффициентов целевой функции без изменения оптимального решения

Вопросы для самопроверки Задания для самостоятельной работы

1.5.Каноническая форма представления области решений задачи линейного программирования

Вопросы для самопроверки

1.6.Решение задачи линейного программирования симплексным методом

Задания для самостоятельной работы

1.7.Интерпретация симплексной таблицы при анализе оптимального решения задачи линейного программирования на чувствительность

1.8.Двойственные задачи линейного программирования

1.8.1.Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов

1.8.2.Взаимно двойственные задачи линейного программирования и их свойства Вопросы для самопроверки

Задания для самостоятельной работы

1.9.Транспортная задача

1.10.Решение транспортной задачи

1.10.1.Определение начального решения

1.10.2.Нахождение вводимой в базис переменной

1.10.3.Нахождение выводимой из базиса переменной

2. Целочисленное линейное программирование

2.1.Задачи целочисленного линейного программирования

2.2.Метод ветвей и границ

Вопросы для самопроверки

Задания для самостоятельной работы

2.3. Метод отсечений (Гомори)

Вопросы для самопроверки Задания для самостоятельной работы

3. Динамическое программирование

3.1.Задача динамического программирования

3.2.Метод решения задач динамического программирования

3.3.Решение задачи линейного программирования методом динамического программирования

Вопросы для самопроверки Задания для самостоятельной работы

4. Нелинейное программирование

4.1.Задачи нелинейного программирования

4.2.Решение задачи нелинейного программирования методом множителей Лагранжа

Вопросы для самопроверки Задания для самостоятельной работы

Список литературы

3

Предисловие

Управление экономической системой реализуется как процесс, подчиняющийся опреде-

ленным закономерностям. Их знание помогает определить условия, необходимые и доста-

точные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. При реше-

нии конкретной задачи управления предполагается построение экономических и математи-

ческих моделей и установление критериев эффективности, позволяющих оценивать преиму-

щество того или иного варианта действия. Для применения количественных методов требу-

ется построить математическую модель и количественно выразить критерий эффективности в виде целевой функции.

Математическое программирование включает методы нахождения экстремума (мини-

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

ограничениями.

Целевая функция – это экономический показатель, зависящий от некоторых факторов.

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

определяющих диапазоны возможных изменений факторов.

Задачами математического программирования являются оптимизационные матема-

тические модели, состоящие из целевой функции от некоторых переменных и ограничений,

представляемых выражениями от тех же переменных.

Будем рассматривать класс оптимизационных моделей. Такие задачи возникают при по-

пытке оптимизировать планирование и управление сложными системами, в первую очередь экономическими системами. Оптимизационную задачу можно сформулировать в общем ви-

(Условия неотрицательности переменных, если они есть, входят в ограничения (1) ).

Оптимальным решением задачи математического программирования является соответ-

ствующий вектору переменных целевой функции и ограничений вектор чисел, для которого выполняются все ограничения, а целевая функция принимает требуемое экстремальное зна-

чение.

Как известно, упорядоченная совокупность значений n переменных x1 , x2 ,...,xn пред-

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

емы, можно применять классические методы оптимизации. Однако применение этих методов весьма ограничено, так как задача определения условного экстремума функции n перемен-

ных технически весьма трудна: метод дает возможность определить локальный экстремум, а

из-за многомерности функции определение ее максимального (или минимального) значения

(глобального экстремума) может оказаться весьма трудоемким – тем более, что этот экстре-

мум возможен на границе области решений. Классические методы вовсе не работают, если множество допустимых значений аргумента дискретно или функция z задана таблично. В

этих случаях для решения задачи (1) - (2) применяются методы математического программи-

рования.

Построение математической модели реального экономического процесса для форми-

рования задачи математического программирования представляет собой скорее искус-

ство, чем науку.

Если показатель эффективности z f x1 , x2 ,...,xn представляет линейную функ-

цию, а функции i x1 , x2 ,...,xn в системе ограничений (1) также линейны, то такая задача является задачей линейного программирования. Если исходя из содержательного смысла, ее решения должны быть целыми числами, то это задача целочисленного линейного програм-

мирования. Если в задаче математического программирования имеется переменная времени и критерий эффективности (2) выражается не в явном виде как функция переменных, а кос-

венно – через уравнения, описывающие протекание процессов во времени, то такая задача является задачей динамического программирования. Если критерий эффективности и (или)

система ограничений задаются нелинейными функциями, то имеем задачу нелинейного про-

граммирования.

Таким образом, задачи математического программирования могут быть классифициро-

ваны:

1)по признаку моделируемых типов процессов,

2)по признаку свойств целевой функции и ограничений.

1) Классификация по признаку моделируемых типов процессов:

1.1) регулирование запасов,

1.2) распределение ресурсов,

1.3) организация обслуживания,

1.4) планирование замены оборудования,

5

1.5) другие, в т.ч. комбинированные процессы.

2) Классификация по признаку свойств используемых функций:

2.1) задача линейного программирования, когда целевая функция и ограничения задают-

ся линейными функциями; 2.2) задача целочисленного программирования, в которой есть ограничения на целочис-

ленность решения; 2.3) задача динамического программирования, целевая функция которой представляет

собой сумму целевых функций каждого этапа ее решения, а ограничения каждого этапа по-

следовательно связаны между собой; 2.4) задача нелинейного программирования, когда целевая функция и ограничения зада-

ются нелинейными функциями.

В пособии нашли отражение основные из приведенных видов задач математического программирования.

Цель курса состоит:

1) в приобретении навыков построения типовых задач математического программиро-

вания,

2) в изучении методов решения типовых задач математического программирования.

В создание современного математического аппарата и развитие многих направлений ма-

тематического программирования большой вклад внесли российские ученые. Особо следует отметить роль академика Л.В.Канторовича, который в 1939 г., занявшись планированием ра-

боты агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудо-

вания, о раскрое материалов с наименьшими потерями, о распределении грузов по несколь-

ким видам транспорта и др. Л.В.Канторович сформулировал новый класс условно-

экстремальных задач и предложил универсальный метод их решения, положив начало ново-

му направлению прикладной математики -линейному программированию.

Методы математического программирования, как и любые математические методы, все-

гда в той или иной мере упрощают, огрубляют задачу. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов математического програм-

мирования, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно приве-

сти в связи с этим шутливо-парадоксальное определение этих методов, сделанное одним из их создателей Т. Саати, как “искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами.”

В данном учебном пособии рассматриваются основные оптимизационные модели экономических процессов. Теоретические положения сопровождаются решением практических задач, вопросами для самопроверки и заданиями для самостоятельной работы.

6

1. Линейное программирование

1.1. Задача линейного программирования

Задача линейного программирования (ЗЛП) сводится к задаче нахождения экстремума линейной целевой функции на области определения, заданной линейными ограничениями.

Рассмотрим типичные задачи, сводящиеся к задачам линейного программирования.

1.1.1. Задача об ассортименте продукции

Словесная формулировка задачи

Фирма выпускает три вида изделий. В процессе производства используются три техно-

логические операции. Показана технологическая схема производства изделий.

Указана длительность технологических операций при изготовлении одного изделия каж-

дого вида, а также ограниченный в сутки фонд рабочего времени, в течение которого опера-

ции 1, 2 и 3 могут быть применены для производства рассматриваемых изделий.

Изучение рынка сбыта показало, что ожидаемая прибыль от продажи одного изделия ви-