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

Автор работы: Пользователь скрыл имя, 22 Ноября 2011 в 18:18, реферат

Описание

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

Содержание

Введение
Постановка основной задачи линейного программирования с n-переменными
Графический метод решения задач линейного программирования с n-переменными
Симплекс-метод решения задач линейного программирования с n-переменными
Математическая модель
Решение задачи в MS Excel
Решение задачи графическим методом
Решение задачи симплекс-методом
Аналитическая часть
Заключение
Список используемой литературы

Работа состоит из  1 файл

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

— 807.00 Кб (Скачать документ)
 

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

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

 

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

     

       

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

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

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

     n-m=4-2=2

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

     

     

     

     

     

     

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

     

     

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

  1. 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
 
     
  1. 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
 
     
  1. 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 денежных единиц. Были выполнены все необходимые ограничения и выявлено в каком количестве стоит производить различные товары.

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

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

Информация о работе Методы решения задач линейного программирования с n-переменными