Практическая часть

Постановка задачи

Торговое предприятие планирует организовать продажу 4 видов товара A, B, C, D, учитывая при этом только два вида ресурсов: рабочее время продавцов в количестве 970 часов и площадь товарного зала 290 м². Плановые нормативы затрат ресурсов в расчете на единицу товара каждого наименования и прибыль от их продажи заданы в таблице.

Показатели	Товары					Общее кол-во ресурсов
	A	B	C	D
Расход рабочего времени на единицу товара, ч		0,62	0,81	0,71	0,43	970
Использование площади торгового зала на единицу товара, м2		0,13	0,22	0,45	0,22	290
Прибыль от продажи единицы товара, руб		30	50	62	40

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

Математическая модель

Пусть x – количество товара, продажу которого планирует организовать торговое предприятие. Тогда x₁ – товар вида A, x₂ – товар вида B, x₃ – товар вида C и x₄ – товар вида D.

0,62x₁+0,81x₂+0,71x₃+0,43x₄ – расход рабочего времени на изготовление товара. Так как этот ресурс ограничен, имеем следующее ограничение: 0,62x₁+0,81x₂+0,71x₃+0,43x_4£970.

0,13x₁+0,22x₂+0,45x₃+0,22x₄ – использование торгового зала на изготовление товара. Так как этот ресурс ограничен, имеем следующее ограничение: 0,13x₁+0,22x₂+0,45x₃+0,22x_4£290.

Кроме того, количество выпущенной продукции не может быть отрицательной, следовательно, x_1³0, x_2³0, x_3³0, x_4³0.

Задача состоит том, чтобы найти значения x₁, x₂, x₃ и x₄ при которых полученная прибыль будет наибольшей. Прибыль обозначим F, тогда

F=30x₁+50x₂+62x₃+40x_4Þmax

Таким образом, получаем следующую экономико-математическую модель задачи линейного программирования:

Решение задачи в 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

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

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

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

1. 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

2. 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

3. 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.