скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

скачать рефератыКурсовая работа: Методы решения задач линейного программирования с n-переменными

линейное программирование прибыль товарооборот


Решение задачи графическим методом

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

n=4 (количество переменных)

m=2 (количество ограничений)

n-m=4-2=2

Выразим две переменные:

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

Найдем координаты прямых.

I.  1266,239-1,191x2-0,203x4=0

1,191x2+0,203x4=1266,239

x2=1063,172-0,17x4

x2

1063,172

893,172

x4

0

1000

II.  278,525-0,16x2-0,431x4=0

0,16x2+0,431x4=278,525

x4=646,229-0,371x2

x2

0

1000

x4

646,229

275,229

III.  55255,72+4,35x2+7,188x4=0

-4,35x2-7,188x4=55255,72

x2= -12702,464-1,652x4

x2

-11050,464

-3817,536

x4

-1000

-10000

Построим область допустимых решений задачи, ограниченную прямыми:

x2=1063,172-0,17x4 (I)

x4=646,229-0,371x2 (II)

x2= -12702,464-1,652x4 (III)

Найдем max:


Рис. 1 График функции

Построим линию уровня 55255,72+4,35x2+7,188x4=0 и вектор градиента (4,35; 7,188). Будем передвигать линию уровня, пока не выйдем из многоугольника, что произойдет в точке A с координатами (1061; 257). В этой точке функция принимает максимальное значение 63330.

Ответ: Чтобы достичь максимальной прибыли предприятие должно выпустить 1061 изделий товара B и 257 изделий товара D.

Решение задачи симплекс-методом

Решим прямую задачу линейного программирования симплекс-методом. Определим максимальное значение целевой функции F(X) = 30x1+50x2+62x3+40x4 при следующих условиях:

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

Выразим базисные переменные x5 и x6 через небазисные.

Переходим к основному алгоритму симплекс-метода.

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

В качестве новой переменной выбираем x3.

Вычислим значения D3 по всем уравнениям для этой переменной

и выберем из них наименьшее:

Вместо переменной x6 в план войдет переменная x3.

Выразим переменную x3 через x6 и подставим во все выражения.

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

Полагая небазисные переменные x5 и x3 равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (-12.09, -19.69, 0, -9.69, 0, 137.78), x0 = 39955.5556

В качестве новой переменной выбираем x2.

Вычислим значения D2 по всем уравнениям для этой переменной.

и выберем из них наименьшее:

Вместо переменной x5 в план войдет переменная x2.

Выразим переменную x2 через x5 и подставим во все выражения.

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

Полагая небазисные переменные x2 и x3 равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (5.56, 0, 0, -6.16, 42.53, 70.67), x0 = 61752.2804

В качестве новой переменной выбираем x4.

Вычислим значения D4 по всем уравнениям для этой переменной.

и выберем из них наименьшее:

Вместо переменной x3 в план войдет переменная x4.

Выразим переменную x4 через x3 и подставим во все выражения.

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

Полагая небазисные переменные x2 и x4 равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (3.27, 0, 15.36, 0, 26.32, 130.38), x0 = 63337.3206

Выражение для x0 не содержит положительных элементов. Найден оптимальный план.

Окончательный вариант системы уравнений:

Оптимальный план можно записать так:

x2 = 1061

x4 = 257.18

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

x2 = 1061

x4 = 257

Максимальная прибыль предприятия:

F(x) = 50*1061 + 40*257= 63330

Ответ: Чтобы прибыль максимальной – 63330 денежных единиц, предприятие должно выпустить 1061 изделий товара B и 257 изделий товара D.


Аналитическая часть

 

Линейное программирование – это раздел исследования операций, в котором изучаются линейные оптимизационные модели, т.е. задачи поиска минимума затрат при условии выполнения необходимого объема работ или максимума прибыли при линейных ограничениях на ресурсы.

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

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

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

Для убеждения в том, что решение выполнено правильно, поставленная задача была решена несколькими методами и проверена в MS Excel.

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

Для наглядности в проекте приводятся скриншоты решения поставленной задачи в MS Excel и подробно расписано решение графического и симплекс-метода.

Решение определило следующий оптимальный план производства товаров:

Для максимизации прибыли, которая составляет 63330 денежных единиц, предприятие должно выпустить 0 изделий товара A, 1061 изделий товара B, 0 изделий товара C и 257 изделий товара D.

По моему мнению, наилучшим методом максимизации, т.е. решения конкретной поставленной передо мной задачи, является симплекс метод решения задач линейного программирования, которого достаточно подробно освещается в основной части теоретического раздела.


Заключение

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

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

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

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


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

1.  Ашманов С.А. Линейное программирование. М.: Наука, 2001.

2.  Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая школа, 1987

3.  http://revolution./emodel/00188498_0.html

4.  Лунгу К.К. Линейное программирование. Руководство к решению задач. – М.: ФИЗМАТЛИТ, 2005.


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


Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

Обратная связь

Поиск
Обратная связь
Реклама и размещение статей на сайте
© 2010.