Методы линейного программирования

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра экономики и менеджмента

КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ «МАТЕМАТИЧЕСКИЕ МЕТОДЫ»

Методы линейного программирования

Выполнил: Никулкина Т.О.

Студентка группы з4072/24

Проверил: Артеменко Е.В.

Санкт-Петербург

2011

СОДЕРЖАНИЕ:

ВВЕДЕНИЕ…………………………………………………………………...3

1. Понятие линейного программирования……………………….…………4

2.Симплекс метод…………………………………………………………….4

3.Экономическая постановка задачи.…………………………….…….…...5

4. Понятие математической модели………….………………………….......5

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

6. Решение исходной задачи  двойственным симплекс методом………….7

Список использованной литературы………………………………………..10

Введение.

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

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

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

Модель задачи математического программирования включает:

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

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

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

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

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

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

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

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

                             1.Понятие линейного программирования.

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

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

2.Симплекс метод

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

3.Экономическая постановка задачи

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

Таблица 1

4.Понятие математической модели.

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

1)                формулировка задачи;

2)                разработка математической модели изучаемой системы;

3)                выбор метода и отыскание решения с помощью этой модели;

4)                проверка решения.

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

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

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

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

Когда задача ЛП поставлена, главная мера эффективности выбрана, функциональная форма математической модели определена. Нужно указать, как выбранные нами переменные связаны с данными задачи, для этого необходимы некоторые эксперименты, позволяющие выявить структуру. В одних случаях, достаточно открыть бухгалтерскую книгу, заглянуть в нужный файл компьютера и получить необходимую информацию; в других, затратить силы и средства. Но в любом случае между переменными и структурой модели существует связь.

Именно посредством модели задачи связана с предлагаемым решением. Насколько точна модель, настолько и реально решение. С помощью математической модели и меры эффективности можно оценить разные решения и выбрать лучшее. В линейном программировании, благодаря вычислительным методам, эта задача решается автоматически.

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

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

Построим ей двойственную задачу по следующим правилам:

1.                   Количество переменных в двойственной задаче равно количеству неравенств в исходной.

2.                   Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

3.                   Столбец свободных членов исходной является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

4.                   Условиям неотрицательности переменных исходной задачи соответствуют неравенства ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам–ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Транспонированной называется матрица, у которой строки и столбцы меняются местами. Поэтому коэффициенты при переменных yi в задаче II это, соответственно, коэффициенты i-ого неравенства в задаче I. Неравенства, находящиеся напротив друг друга, называются сопряженными.

Двойственность является фундаментальным понятием в теории линейного программирования. Основные результаты теории двойственности заключены в двух теоремах, называемых теоремами двойственности.

Теорема 1

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*)=G(y*), где х*, у* – оптимальные решения задачи I и II

Теорема 2

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

6. Решение исходной задачи  двойственным симплекс методом

Двойственный симплекс–метод основан на очень простой идее. Поскольку, решая исходную задачу, мы автоматически получаем решение двойственной, то иногда удобно выбирать, какую из задач решать, естественно, более простую по форме, а затем, решив, находим оптимальное решение другой. Этот метод удобно применять при решении задачи о рационе, задачи о раскрое и некоторых других ЗЛП

Имеем задачу  (I) построим ей двойственную (II).

I.                                              II.

F=2X1+X2min                                     G=24Y1 + 18Y2 + 20Y3 + 6Y 4max

Приведем ее к каноническому виду.

Введем базисные переменные ,

G=- G = -24Y1 - 18Y2 - 20Y3 - 6Y 4 min

Решаем симплекс–методом задачу .

1.Найдем разрешающий элемент.

1.1.              Из отрицательных элементов индексной F– строки выберем наибольший по модулю, назовем соответствующий ему столбец – разрешающим.

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

В нашем примере, , элемент 3 – разрешающий. Строка, соответствующая этому элементу тоже называется разрешающей.

2. Выбрав разрешающий элемент, делаем перечет таблицы по правилам:

2.1.              В новой таблице, таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В данной задаче: Y 1 входит в базис, вместо Y 5, которая выходит из базиса, и теперь свободная.

2.2.              На месте разрешающего элемента  записываем обратное ему число .

2.3.              Элементы разрешающей строки делятся на разрешающий элемент.

2.4.              Элементы разрешающего столбца делятся на разрешающий элемент и записываются с противоположным знаком.

2.5.              Чтобы заполнить оставшиеся элементы, осуществляем пересчет по правилу прямоугольника.

Пусть мы хотим посчитать элемент, стоящий на месте 2(Y2;Y6 )

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

Итак, . Записываем на место, где было 3.

Проверим целевую функцию, согласно условиям.

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

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

Выписываем решение:

Y1=  0;                Y4=-3;

Y2=  2;                Y5= 0;

Y3 =  0;                Y6= 0;

Подставляем полученные решения в условия задачи: 

     I.                       II.

Два условия в II системе не совпадают, выписываем из в I системы эти условия и решаем как систему уравнений.

F=2X1+X2min     = 2*6+6 = 18                       

Ответ к задаче:

Для эффективного откорма крупно рогатого скота необходимо 6 кг зерна и 6 кг отрубей. При этом затраты минимальны и составят 18 руб.

8

Список используемой литературы

1.       Лищенко «Линейное и нелинейное программирование», 1987

2.       А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», 1987

3.        Экономико-математические методы и прикладные модели: Учебное пособие для вузов / Под ред. В.В. Федосеева. - М.: ЮНИТИ, 1999.

4.        Орлова И.В., Половников В.А., Федосеев В.В. Курс лекций по эко­номике математическому моделированию. - М.: Экономическое образование, 1993.

5.        Орлова И.В. Экономико-математические методы и модели. Выпол­нение расчетов в сфере Excel: Практикум. - М.: Финстатинформ, 2000.

6.        Федосеев В.В., Эриашвили Н.Д. Экономико-математические мето­ды и модели в маркетинге: Учебное пособие для вузов / Под ред. В.В. Федосеева. - 2-е изд., перераб. и доп. - М.: ЮНМТИ-ДАНА, 2001.

7.        Федосеев В.В., Гармаш А.Н., Орлова И.В., Половников У.А Экономико-ма­тематические методы и прикладные модели. 2-е изд. - М.: ЮНИТИ-ДАНА, 2005.

8.        Половников В.А., Орлова И.В., Гармаш А.Н. Экономико-математические методы и прикладные модели: Методические указания по выполнению конт­рольной работы, темы и задачи. - М.: ВЗФЭИ, 2002.

9.        Гармаш А.Н., Гусарова О.М. Орлова И.В., Якушев А.А. Экономимо-матема­тические методы и прикладные модели: Компьютерный практикум и руко­водство к выполнению лабораторной работы по теме «Оптимизационные экономико-математические модели. Методы получения оптимальных реше­ний». - М. - ВЗФЭИ. 2002.

10.    Орлова И.В. Экономико-математическое моделирование. Практическое посо­бие по решению задач - M.: ВЭФЭИ: Вузовский учебник. 2004.

8