Решение задачи в MS Excel

 

В качестве значений переменных x₁, x₂, x₃, x₄ будем использовать ячейки $B$12:$B$15. Для значения целевой функции будем использовать ячейку $C$16.

В целевую ячейку $C$16 впишем формулу: B5*B12+C5*B13+D5*B14+E5*B15.

В ячейку $C$12 впишем формулу прибыли от товара A: B5*B12.

В ячейку $C$13 впишем формулу прибыли от товара B: C5*B13.

В ячейку $C$14 впишем формулу прибыли от товара C: D5*B14.

В ячейку $C$15 впишем формулу прибыли от товара D: E5*B15.

В ячейку $G$3 впишем формулу ограничения расхода рабочего времени: B3*B12+C3*B13+D3*B14+E3*B15.

В ячейку $G$4 впишем формулу ограничения использования площади торгового зала: B4*B12+C4*B13+D4*B14+E4*B15.

 

Рис. 1 Компьютерная модель задачи

 

Далее выбираем пункт меню Сервис/Поиск решения:

 

Рис. 2 Окно поиска решения

 

Перед нами открывается диалоговое окно Поиск решения. В нём указываем, что нам необходимо установить ячейку $ C $16 максимальному значению, изменяя ячейки $ B $12:$ B $15. Далее нажимаем кнопку Добавить для добавления ограничений. И добавляем следующие ограничения:

 

Рис. 3 Добавление ограничений

 

Ограничения по расходу рабочего времени на единицу товара.

После ввода каждого ограничения нажимаем кнопку Добавить. После ввода последнего ограничения нажимаем кнопку OK. И диалоговое окно Поиск решения принимает следующий вид:

 

Рис. 4 Окно поиска решения, после ввода ограничений

 

Задаем параметры поиска решения:

 

Рис. 5 Измененеие параметров поиска решения

 

Нажимаем кнопку Выполнить. И перед нами открывается диалоговое окно Результаты поиска решения:

 

Рис. 6 Выбираем отчет по результатам

 

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

 

Товар	Кол-во	Прибыль
A	0	0
B	1061	53050
C	0	0
D	257	10280
Стоимость продукции		63330

Рис. 7 Результат выполнения поиска решения

Отчет по результатам

Microsoft Excel 11.0 Отчет по результатам
Рабочий лист: [Лююю.xls]Лист1
Отчет создан: 15.02.2011 11:47:21
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$C$16	Стоимость продукции Прибыль	63337,32057	63330
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$B$12	A Кол-во	0	0
	$B$13	B Кол-во	1061,004785	1061
	$B$14	C Кол-во	0	0
	$B$15	D Кол-во	257,1770335	257
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$A$20	Расход рабочего времени на единицу товара, ч	969,92	$A$20<=$F$3	не связан.	0,08
	$B$20	Использование площади торгового зала на единицу товара, м2	289,96	$B$20<=$F$4	не связан.	0,04
	$B$15	D Кол-во	257	$B$15>=0	не связан.	257
	$B$14	C Кол-во	0	$B$14>=0	связанное	0
	$B$12	A Кол-во	0	$B$12>=0	связанное	0
	$B$13	B Кол-во	1061	$B$13>=0	не связан.	1061
	$B$12	A Кол-во	0	$B$12=целое	связанное	0
	$B$13	B Кол-во	1061	$B$13=целое	связанное	0
	$B$14	C Кол-во	0	$B$14=целое	связанное	0
	$B$15	D Кол-во	257	$B$15=целое	связанное	0

 

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

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

 

 

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

 

 

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

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

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

n-m=4-2=2

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

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

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

I. 1266,239-1,191x₂-0,203x₄=0

1,191x₂+0,203x₄=1266,239

x₂=1063,172-0,17x₄

 

x2	1063,172	893,172
x4	0	1000

 

II. 278,525-0,16x₂-0,431x₄=0

0,16x₂+0,431x₄=278,525

x₄=646,229-0,371x₂

 

x2	0	1000
x4	646,229	275,229

 

III. 55255,72+4,35x₂+7,188x₄=0

-4,35x₂-7,188x₄=55255,72

x₂= -12702,464-1,652x₄

 

x2	-11050,464	-3817,536
x4	-1000	-10000

 

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

x₂=1063,172-0,17x₄ (I)

x₄=646,229-0,371x₂ (II)

x₂= -12702,464-1,652x₄ (III)

Найдем max:

 

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

 

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

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

 

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

 

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

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

Выразим базисные переменные x₅ и x₆ через небазисные.

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

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

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

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

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

Вместо переменной x₆ в план войдет переменная x₃.

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

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

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

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

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

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

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

Вместо переменной x₅ в план войдет переменная x₂.

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

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

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

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

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

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

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

Вместо переменной x₃ в план войдет переменная x₄.

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

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

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

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

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

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

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

x₂ = 1061

x₄ = 257.18

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

x₂ = 1061

x₄ = 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.