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

Министерство  образования и  науки Российской Федерации

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

  УНИВЕРСИТЕТ

Кафедра прикладной математики и информатики

 
 
 
 

Курсовая  работа

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

Тема: «Решение задачи линейного программирование в среде Excel» 
 
 
 
 
 
 

Выполнил: студент  2 курса, 24 группы

Амиров  Р.М.

Научный руководитель:

кандидат  технических наук, доцент Козлов Г.В. 
 
 
 
 

Москва 2008

Содержание:

  Введение…………………………………………………………………2

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

2.Решение задачи  линейного программирования в  Excel………………6

Заключение…………………………………………………………………9

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

Введение

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

      Линейное  программирование представляет собой  наиболее часто используемый метод  оптимизации. К числу задач линейного программирования можно отнести задачи:

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

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

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

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

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

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

    Так как функция линейна, то . (*)

    Выберем среди точек  ту, в которой линейная форма принимает наименьшее значение. Пусть это будет точка . Обозначим минимальное значение функции в угловой точке через z^*:

     .

    Подставим данное значение функции в линейную форму (*) вместо и получим:

     .

    Так как  - оптимальная точка, то получили противоречие: (!). Следовательно, , - угловая точка.

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

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

 

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

     Для задач с числом переменных не более двух может быть применён графический метод, очень простой,  наглядный лёгкий дл усвоения. Для большего, чем  два количества переменных применяется «симплекс-метод», заключающийся в последовательном построении симплекс-таблиц вплоть до получения приемлемого результата. Понять до конца симплекс-метод без специального математического образования невозможно, но как чётко сформулированный рецепт он вполне приемлем. Решение задач линейного программирования превращается в легкую увлекательную прогулку в приложение Excel под названием «Поиск решения» или «Solver». От пользователя требуется лишь грамотно сформулировать свою задачу в предложенном Excel’ом стиле. Решение с отчетом и комментариями появляется за считанные секунды.

     Теперь  цель наших усилий ясна. Будем  учиться ставить задачи линейного  программирования и решать их  на Excel’e.

       Начнём с задачи о питании.

  Студент решил, что для поддержания нормальной жизнедеятельности ему необходимо получать не менее 3 ккал энергии и 4 ед.белка. Все  это он решил заимствовать, питаясь хлебом с сыром. Ему известно, что 1 кг хлеба стоит 2,5 рубля и содержит 5 ккал и 20 ед.белка. Составить оптимальный рацион ежедневного питания, а именно, определить, какое количество хлеба и сыра необходимо покупать, чтобы при минимальных денежных затратах обеспечить удовлетворение потребности организма в килокалориях и белках. Указать величину этих затрат.

Решение:

Дневные денежные затраты:

Z=2.5X₁+16X₂

Минимальные потребности  организма в белках и килокалориях:

3X₁+5X₂≥3

3X₁+20X₂≥4 

15X₂≥1

X₂≥1/15

X₂≥0,067 

3X₁≥3-5X₂

X₁≥ (3-5X₂)/3

X₁≥0,889

Отсюда:

Z=2,5*0,89+16*0,067=3,288 

После получения  результатов ручным способом подготовим следующую справочную информацию:

 

В выбранные  ячейки С6 – Е6 записываем соответствующие функции и включаем приложение «Поиск решений», который открывается в меню «Сервис». Далее следуем рекомендациям приложения. Получаем следующие данные: ² 
 

 

Отчёт по результатам  применения функции «Поиск решения»:

Заключение 

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

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

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

2.Князев А.С. «Прикладные задачи современной экономики»,  М.:2006