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

Раздел

Теоретические основы экономико-математического моделирования

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

1.2 Первая и вторая теория двойственности

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

Раздел

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

 2.1 Графический метод

 2.2 Симплекс метод

 2.3 Двойственные задачи

Раздел

Применение экономико-математического моделирования для обоснования      

плановых прогнозных решений.

Заключение

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

      

 

 

Введение

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

И всем интересно понять, и чем тут дело: почему одни — в пучине, а другие — на поверхности?

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

Но вот как тогда объяснить еще более внушительный и масштабный результат в бизнесе, полученный тщедушными ин­теллектуалами: математиками, физиками, инженерами, которых трудно заподозрить в "уголовке"?

Считать сегодня умеют, конечно, все. Но этот счет, увы, очень часто ограничивается умением складывать и умножать.

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

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

И дело здесь не только в умении правильно выстроить ко­лонки цифр. Современный бизнес требует современного эконо­мического мышления, в немалой степени основанного на спе­циальных математических методах. Доход, прибыль, налог, ссу­да, дивиденд, рентабельность – все это цифры, и тут без хоро­шей математики просто не обойтись: чем правильнее расчет, тем прибыльнее результат.

Соединение экономики бизнеса с математическими рас­четами получило название экономико-математических методов.

 

1 Раздел

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

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

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

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

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

Экономико-математические методы стали применяться относи­тельно недавно. В 1925—1926 гг. в нашей стране был составлен шахматный баланс народного хозяйства, где нашли отражение идеи межотраслевого баланса производства и распределения про­дукции.

В 1939 г. Л. В. Канторович решил задачу оптимальной загруз­ки -станков деревообделочного предприятия с целью получения, максимума продукции. По существу, это была первая задача ли­нейного программирования. Позднее (1947 г.) аналогичную зада­чу разработал и решил американский математик Дж. Данциг. Сама задача была им названа общей задачей линейного програм­мирования, а метод решения – симплексным.

В нашей стране широкие экономические исследования с при­менением математических методов начались в 1958 г., когда ака­демик В. С. Немчинов организовал небольшую лабораторию эко­номико-математических методов, которая вскоре переросла в Цен­тральный экономико-математический институт (ЦЭМИ) АН СССР. Начиная с 50-х годов вопросами оптимального программирования экономики занимался профессор В.В. Новожилов. Большие аграрио-экономические исследования с применением математических ме­тодов проведены проф. М. Е. Браславцем, И. Г. Поповым, Р. Г. Кравченко и другими.

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

 

1.2 Первая и вторая теорема двойственности.

    Первая теорема двойственности

Основная теорема двойственности линейного программирования. Пусть рассматривается пара двойственных задач:

(1) (2)

                              

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

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

Доказательство: Пусть основная задача (1) имеет конечное решение и получена окончательная симплексная таблица:

 

Так как данная таблица, по предположению, соответствует оптимальному решению задачи (1), то и . При этом достигается при .

Рассмотрим полученную таблицу двойственной задачи. Полагая значения переменных слева (небазисных) равными нулю:

,

найдем , …, , , …, . Следова­тельно, получено опорное решение:

, …, , , …, .

Из последнего столбца,

в точке

будет минимальным в силу того, что , . Следовательно, .

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

,

то есть система ограничений двойственной задачи противоречива. Так как из неотрицательности следует неположительность (нельзя сделать ее положительной). То есть, система несовместна.

Теорема доказана.

     

Вторая теорема двойственности       

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

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

Т.е. оптимальные решения и пары двойственных задач удовлетворяют условиям

(1)

(2)

Доказательство: Пусть и – оптимальные решения пары двойственных задач. Тогда для

,

они удовлетворяют следующим ограничениям:

. (3)

Умножим (3), соответственно, на и , и просуммируем полученные выражения:

. (4)

Из основной теоремы двойственности следует

. (5)

И с учетом (4) получаем:

,

.

Первое из этих выражений можем переписать в виде

,

и так как все и выражения в скобках неотрицательны, то опуская å, получим:

.

Аналогично получим:

 

.

Что и требовалось доказать.

Справедлива и обратная теорема.

 

 

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

Для эффективного ведения животноводства большое значение имеет правильное использование кормов в стойловый период, ко> торый продолжается 7—8 месяцев в году, т. с. 60—70% всего времени продуктивного использования животных. В этот период имеется несколько видов кормов, что позволяет находить наилуч­шее их сочетание для разных видов и групп животных. Места складирования и места потребления отдельных видов кормов не всегда совпадают, что требует при их распределении учитывать как потребности животных в кормах, так и затраты на их транс­портировку.

В сельскохозяйственных предприятиях на стойловый период ежегодно составляется план использования заготовленных и за­купаемых кормов по видам, половозрастным группам животных, а также по фермам или отделениям.

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

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

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

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

1) виды кормов и кормовых добавок, которыми располагает
хозяйство на планируемый период;

2) виды минеральных, витаминных добавок и возможность их
приобретения;

3) виды скота и птицы, разводимых в хозяйстве, и деление их
на основные половозрастные и хозяйственные группы;

4) продуктивность и нормы кормления в расчете на одну го­
лову по различным половозрастным группам, по видам животных
и птицы;

5) предельно допустимые границы содержания отдельный кор­мов  или групп кормов в рационе кормления различных половоз­растных групп по видам животных и птицы;

6) количество кормо – дней пребывания различных половозраст­ных групп в хозяйстве на планируемый период;

7) предельно допустимые нормы ввода кормов, минеральных
и витаминных добавок в рацион различных половозрастных
групп но видам животных и птицы;

8) себестоимость кормов и цены на животноводческую про­дукцию;

9) затраты на доставку кормов от места хранения до места
скармливания.

 

              

2 Раздел.

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

2.1 Графический метод

 

Рассмотрим задачу линейного программирования относительно двух неизвестных:

где (2.1) – целевая функция задачи, (2.2) – основные ограничения, (2.3) – условия не отрицательности переменных.

Неравенствам (2.2) на плоскости соответствуют полуплоскости. Чтобы их построить, необходимо сначала построить прямые, отделяющие эти полуплоскости. Уравнения отделяющих прямых получаем их соответствующих неравенств путём замены знака неравенств на " = ". Отделяющие прямые лучше строить по двум точкам, которые являются точками пересечения с осями координат (у этих точек одна из координат равна нулю).

Чтобы выбрать полуплоскость, соответствующую заданному неравенству, достаточно проверить, принадлежит ли точка начала координат (0,0) полуплоскости, подставив координаты (0,0) в неравенство. Если неравенство окажется справедливым, то принадлежит, в противном случае – нет.

Неравенства (2.2) должны выполняться одновременно. Это означает, что решение задачи будет лежать сразу на всех построенных полуплоскостях. С математической точки зрения это равносильно тому, что решение принадлежит пересечению построенных полуплоскостей.

Условие не отрицательности переменных (2.3) требует, чтобы из пересечения полуплоскостей выбрали ту часть, которая лежит в 1 – ой четверти.

Целевая функция (2.1), как функция от двух переменных имеет пространственное представление. Для изображения её на плоскости используют линии уровня, уравнения которых получаем из целевой функции, приравнивая её к различным числовым значениям:

с₁х₁ + с₂х₂ = с, где с Î (– ∞, + ∞ ).                                        (2.4)

Достаточно построить две линии уровня (выбрав произвольные значения С), чтобы, сравнив на них значения целевой функции, определить направление max или min.

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

 

Решим задачу линейного программирования

 

              2.2. f(x) = – x₁→ max (min)

        

 

Строим отделяющие прямые.

1-я отд. прямая

2х₁+х₂=4

х₁=0; х₂=4 (0;4)

х₂=0; х₁=2 (2;0)

 

2-я отд. прямая

2х₁+х₂=8

х₁=0; х₂=8 (0;8)

х₂=0; х₁=4 (4;0)

 

3-я отд. прямая

х₁-2х₂=3

х₁=0; х₂=-1,5 (0;-1,5)

х₂=0; х₂=3  (3;0)

 

4-я отд. прямая

-х₁+2х₂=6

х₁=0;х₂=3 (0;3)

х₂=0; х₁=-6 (-6;0)

 

Линии уровня

1-я линия

-х₁=5

х₁=-5

 

2-я линия

-х₁=-5

Х₁=5

 

При решении задачи на максимум целевая функция достигнет своего оптимального значения в точке А, а на минимум в точке В. Найдем координаты этих точек.

А=(1-я отд.  прямая) (4 отд. прямая)

2х₁+х₂=4     х₂=4-2х₁                               -5х₁= -2 х₂= 4-0,8   

-х₁+2х₂=6  - х₁+2(4-2 х₁)=6       х₁= 0,4   х₂= 3,2

 

А(0,4; 3,2)

 

В(2-я отд.  прямая) (3-я отд.  прямая) 

2х₁+х₂=8  х₁= 3+2х₂                         х₁=3+0,8

х₁ - 2х₂=3 2(3+2х₂) + х₂=8    х₁= 3,8

                5х₂= 2

                х₂= 0,4         

В(3,8; 0,4)

F (max) А            -0,4

F (min) В       -3,8

 

2.2 Симплекс метод

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

Симплекс – метод применяют к задачам линейного программирования, заданным в каноническом виде, где элементы вектора правых частей ограничений принимают неотрицательные значения:

                                      (3.1)