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

       Матрица коэффициентов при неизвестных в ограничениях исходной задачи в двойственной транспонируется ( ). 

. 

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

 

       2.6 Решение двойственной задачи по теоремам

двойственности 

       1) Для любых допустимых планов

       

 и 

исходной и  двойственной задач соответственно значение целевой функции в задачи максимизации не больше значения целевой функции в задачи максимизации.

       2) Если исходная и двойственная задачи имеют допустимые планы, то существуют и оптимальные планы у этих задач.

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

       4) (вторая основная теорема двойственности). Для того чтобы допустимые планы пары двойственных задач были оптимальными, необходимо выполнение условий:

 

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

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

       Рассмотрим  исходную задачу (4).

       Двойственная  задача к исходной представляет собой задачу (5).

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

 имеет место равенство

       Подставим в ограничения задачи (4) значения переменных , , в оптимальном плане: 

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

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

 

       Решив систему, найдем  

 

       Оптимальный план двойственной задачи:

       Согласно  первой основной теореме двойственности  

 

       2.7 Использование программных средств для решения задач линейного программирования 

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

 

       

   Рисунок 2 - Решение задачи линейного программирования с помощью среды MathCAD

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

       Вводим  все ограничения и приравниваем их к правой части неравенства. Целевую  функцию приравниваем к C (константа). Затем вычисляем значения и . Функция find используется для нахождения координат. Введем имя функции и присваиваем ей полученное значение.

       Программа Simplex позволяет решать задачи линейного программирования.

Рисунок 3 - Решение задачи линейного программирования с помощью программы Simplex 

       Выбираем  нужный размер матрицы, в элементы матрицы вводим значения ограничений. Вводим элементы матрицы и устанавливаем ее значение (min или max).Нажимаем «Вычислить», значения можем вычислять автоматически или вручную. Результат выводится в виде таблицы с оптимальным или неоптимальным решением.

       MS Excel – программа, которая тоже позволяет решать задачи линейного программирования.

Рисунок 4 - Решение задачи линейного программирования с помощью программы MS Excel

 

ЗАКЛЮЧЕНИЕ 

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

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

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

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

 

СПИСОК  ЛИТЕРАТУРЫ 

       1 Агальцова, В.П. Математические методы в программировании [Текст] : учебник / Агальцова В.П., Волдайская И.В. - М. : ИД «ФОРУМ»: ИНФРА – М, 2006 – 224 с. : ил.

       2 Кремер, Н.Ш. Исследование операций  в экономике [Текст] : учеб. пособие / Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. ; под ред. Н.Ш. Кремера – М.: ЮНИТИ, 2006. – 407 с.

       3 Орлова, И.В. Экономико – математические  методы и модели: компьютерное моделирование [Текст] : учеб. пособие / Орлова И.В., Половников В.А. – М. : Вузовский учебник, 2007. – 365 с.

       4 Малик, Г.С. Основы экономики и математические методы в планировании [Текст] : учебник / Малик Г.С. - М.: Высшая школа, 2000. – 279 с.: ил.

5 Хазанова, Л.Э. Математические методы в экономике [Текст] : учеб. пособие / Хазанова Л.Э. – М.: Волтерс Клувер, 2005. – 144 с