Реферат: Анализ экономических задач симплексным методом

Реферат: Анализ экономических задач симплексным методом

Введение.

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

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

Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием опти­мальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет матема­тическую модель. Математическая модель задачи — это отражение ори­гинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:

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

2)   целевую функцию (функцию цели, показатель эф­фективности, критерий оптимальности, функционал зада­чи и др.). Целевая функция позволяет выбирать наилуч­ший вариант -из множества возможных. Наилучший ва­риант доставляет целевой функции экстремальное значе­ние. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень об­служивания или дефицитности, число комплектов, отходы и т. д.;

Эти условия следуют из огра­ниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы. Таковыми могут быть возможности технического, техноло­гического и вообще научного потенциала. Нередко по­требности превышают возможности их удовлетворения. Математически ограничения выражаются в виде уравне­ний и неравенств. Их совокупность образует область до­пустимых решений (область экономических возможно­стей). План, удовлетворяющий системе ограничений зада­чи, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, на­зывается оптимальным. Оптимальное решение, вообще говоря, не обяза­тельно единственно, возможны случаи, когда оно не су­ществует, имеется конечное или бесчисленное множество оптимальных решений.

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

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Кан­торовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в эконо­мике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (ме­тода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

1)   умение находить начальный опорный план;

2)   наличие признака оптимальности опорного пла­на;

3)   умение переходить к нехудшему опорному плану.

§1.Задача линейного программирования  и свойства ее решений.

1.1 Понятие линейного программирования. Линейное про­граммирование—раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополни­тельных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на уни­версальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного про­граммирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.

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

Формы записи задачи линейного программирования:

Общей задачей линейного программирования называют задачу

  (1)

при ограничениях

  (2)

  (3)

       (4)

     (5)

- произвольные    (6)

где - заданные действительные числа; (1) – целевая функция; (1) – (6) –ограничения;

 - план задачи.

1.2 Свойства решений.

Пусть ЗПЛ представлена в следующей записи:

          (7)

     (8)

                     (9)

Чтобы задача (7) – (8) имела решение, системе её ограничений (8) должна быть совместной. Это возможно, если  r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r= n система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки много­гранных решений. Пусть r<n. В этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линей­ная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r век­торам базиса, называют, как известно, базисными и обо­значают БП. Остальные n – r переменных будут свобод­ными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свобод­ными будут переменные .

Если свободные переменные приравнять нулю, а базис­ные переменные при этом примут неотрицательные значе­ния, то полученное частное решение системы (8) назы­вают опорным решением (планом).

Теорема. Если система векторов  содер­жит m линейно независимых векторов , то допустимый план    (10) является крайней точкой многогранника планов.

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

§2.Графический способ решения ЗЛП.

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

Пусть дана задача

           (11)

         (12)

                         (13)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (12), (13) задает на плоскости некоторую полуплоскость. Полу­плоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множест­вом. Отсюда следует, что область допустимых решений задачи (11) — (13)  есть выпуклое множество.

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — не­пустое множество, например многоугольник .

 Выберем произвольное значение целевой функ­ции . Получим . Это уравнение пря­мой  линии. В точках прямой NМ целевая функция сохра­няет одно и то же постоянное значение . Считая в ра­венстве (11)  параметром, получим уравнение семей­ства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Найдём частные производные целевой функции по  и

           (14)

           (15)

Частная производная (14)  ((15)) функции пока­зывает скорость ее возрастания вдоль данной оси. Следо­вательно,  и — скорости возрастания  соответст­венно вдоль осей  и . Вектор  называ­ется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор —  указывает направление наискорейшего убывания целевой функции. Его называют антигра­диентом.

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

Из геометрической интерпретации элементов ЗЛП вы­текает следующий порядок ее графического решения.

1.          С учетом системы ограничений строим область до­пустимых решений

2.          Строим вектор  наискорейшего возра­стания целевой функции — вектор градиентного направ­ления.

3.          Проводим произвольную линию уровня   

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

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

§3.Симплексный метод.

Общая идея симплексного метода (ме­тода последовательного улучшения плана) для решения ЗЛП состоит

1)   умение находить начальный опорный план;

2)   наличие признака оптимальности опорного пла­на;

3)   умение переходить к нехудшему опорному плану.

Пусть ЗЛП представлена системой ограничений в каноническом виде:

.

Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.

Пусть система ограничений имеет вид

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

,

 которая имеет предпочтительный вид

.

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

Пусть далее система ограничений имеет вид

Сведём её к эквивалентной вычитанием дополнительных переменных     из левых частей неравенств системы. Получим систему

Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные  входят в левую часть (при ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план  не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограниче­ний-равенств, не имеющих предпочтительного вида, добав­ляют искусственные переменные . В целевую функцию переменные , вводят с коэффициентом М в случае реше­ния задачи на минимум и с коэффициентом -М для за­дачи на максимум, где М - большое положительное число. Полученная задача называется М-задачей, соот­ветствующей исходной. Она всегда имеет предпочти­тельный вид.

Пусть исходная ЗЛП имеет вид

             (1)

         (2)

                      (3)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

           (4)

                      (5)

    ,  ,                  (6)

Страницы: 1, 2, 3