Тушавин В. А.
20 ноября 2015 г.
Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно.
Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.
Наименование ресурса | A | B | Объем ресурсов |
---|---|---|---|
Часы маш.обработки | 3 | 10 | 330 |
Единиц сырья | 16 | 4 | 400 |
Единиц труда | 6 | 6 | 240 |
Николай хочет построить модель с тем, чтобы определить количество единиц продуктов А и В, которые он доложен производить в следующем месяце для максимизации маржинальной прибыли.
Существует целевая переменная (обозначим её Z), которую необходимо оптимизировать, то есть максимизировать или минимизировать (например, прибыль, выручка или расходы). Николай стремится максимизировать маржинальную прибыль, следовательно, целевая переменная:
Z --- это суммарная маржинальная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.
Существует ряд неизвестных искомых переменных (обозначим их х1, х2, х3 и пр.), чьи значения необходимо определить для получения оптимальной величины целевой функции, которая, в нашем случае является суммарной маржинальной прибылью. Эта маржинальная прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:
х1 --- количество единиц продукта А, произведенных в следующем месяце.
х2 --- количество единиц продукта В, произведенных в следующем месяце.
Очень важно четко определить все переменные величины; особое внимание уделите единицам измерения и периоду времени, к которому относятся переменные.
Целевая функция --- это линейное уравнение, которое должно быть или максимизировано или минимизировано. Оно содержит целевую переменную, выраженную с помощью искомых переменных, то есть Z выраженную через х1, х2, ... в виде линейного уравнения.
В нашем примере каждый изготовленный продукт А приносит 2500 руб. маржинальной прибыли, а при изготовлении х1 единиц продукта А, маржинальная прибыль составит 2500х1. Аналогично маржинальная прибыль от изготовления х2 единиц продукта В составит 3500х2. Таким образом, суммарная маржинальная прибыль, полученная в следующем месяце за счет производства х1 единиц продукта А и х2 единиц продукта В, то есть, целевая переменная Z составит: Z = 2500х1+3500х2.
Николай стремится максимизировать этот показатель. Таким образом, целевая функция в нашей модели:
Ограничения – это система линейных уравнений и/или неравенств, которые ограничивают величины искомых переменных. Они математически отражают доступность ресурсов, технологические факторы, условия маркетинга и иные требования. Ограничения могут быть трех видов: «меньше или равно», «больше или равно», «строго равно».
В нашем примере для производства продуктов А и В необходимо время машинной обработки, сырье и труд, и доступность этих ресурсов ограничена. Объемы производства этих двух продуктов (то есть значения х1 и х2) будут, таким образом, ограничены тем, что количество ресурсов, необходимых в производственном процессе, не может превышать имеющееся в наличии. Рассмотрим ситуацию со временем машинной обработки. Изготовление каждой единицы продукта А требует трех часов машинной обработки, и если изготовлено х1, единиц, то будет потрачено Зх1, часов этого ресурса.
Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено х2 продуктов, то потребуется 10х2 часов. Таким образом, общий объем машинного времени, необходимого для производства х1 единиц продукта А и х2 единиц продукта В, составляет 3х1+10х2. Это общее значение машинного времени не может превышать 330 часов. Математически это записывается следующим образом:
3х1+10х2≤330
Аналогичные соображения применяются к сырью и труду, что позволяет записать еще два ограничения:
16х1+4х2≤400
6х1+6х2≤240
Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:
х2≥12
Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств х1≥0 и х2≥0. В нашем примере второе условия является избыточным, так как выше было определено, что х2 не может быть меньше 12.
Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:
Симплексный метод является универсальным методом решения задачи линейного грограммирования, так как позволяет решить практически любую задачу, представленную в каноническом виде.
Идея симплексного метода заключатся в том, что, начиная с некоторого опорного решения, осуществляется последовательно направленное перемещение по опорным решениям системы к оптимальному опорному решению. Так как число опорных решений конечно, то через конечное число шагов оптимальное решение будет найдено.
Алгорим симплексного метода можно описать следующим образом:
- Привести задачу к каноническому виду
- Найти неотрицательное базисное решение системы ограничений
- Рссчитать оценки свободных переменных по формуле:
$${\Delta}j = \sum\limits{i = 1}^r c_ih_{ij} - c_j ,;j = \overline {1,n} ,$$
где hij -- коэффициенты при свободной переменной xj,
ci -- коэффициенты при базисных переменных в целевой функции,
cj -- коэффициенты при свободной переменной в целевой функции,
- Проверить найденное опорное решение на оптмальность:
а) если все оценки
б) если хотя бы одна оценка j нет ни одного положительного коэффициента, то задача не имеет оптимального решения из-за ограниченности целевой функции
в) если хотя бы одна оценка j есть хотя бы один положительный коэффициент, то решение не оптимально и его можно улучшить переходом к новому базису. Если отрицательных оценок несколько,то в базис ввести переменную с наибольшей по абсолютной величине отрицательной оценкой.
Приведем задачу к каноническому виду.
Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:
Б.п. | x |
x |
x |
x |
x |
x |
b |
---|---|---|---|---|---|---|---|
x |
3 | 10 | 1 | 0 | 0 | 0 | 330 |
x |
16 | 4 | 0 | 1 | 0 | 0 | 400 |
x |
6 | 6 | 0 | 0 | 1 | 0 | 240 |
x |
0 | -1 | 0 | 0 | 0 | 1 | 12 |
Проверим данное решение на оптимальность, для этого найдем свободные переменные в симплексной таблице. Вычисления представлены в файле lp_simplex.xlsx.
Данное решение не оптимально, поскольку в нижней строчке есть отрицательные значения. Поскольку имеются положительные коэффициенты, решение можно улучшить, для этого введем в базис переменную x2. Так как в колонке x2 имеется несколько положительных коэффициентов, то определяем отношение свободного члена bi к соответсвующим коэффициентам в данной колонке и выбираем наименьший результат.
Преобразуем таблицу и повторим расчет.
Данное решение не оптимально, поскольку в нижней строчке есть отрицательные значения. Поскольку имеются положительные коэффициенты, решение можно улучшить, для этого введем в базис переменную x1.
Полученное решение ( 10; 30) является оптимальным.
Решение в Excel осуществляется с помощью надстройки "Поиск решения", также использующей симплекс-метод.
Файл с решением lp_solve.xlsx
Анологично даную задач можно решить с помощью Решателя в LibreOffice. Следует отметить, что в LibreOffice нет ограничений на число переменных, в отличии от Excel.
Для решения задач линеного программирования в GNU R можно использовать следующие пакеты:
- lpSolve
- linprog
Второй пакет является надстройкой над первым и позволяет выводить больше диагностической информации
library(lpSolve) # Подключили библиотеку
f.obj <- c(2500, 3500) # Описали целевую функцию
names(f.obj) <-c("A","B")
a.mat<-rbind(c(3,10), # матрица
c(16,4), # коээфициентов
c(6,6), # при ограничениях
c(1,0),
c(0,1))
a.dir<-c("<=","<=","<=",">=",">=")
b.vec<-c(330,400,240,0,12) # вектор ограничений
result<-lp ("max", f.obj, a.mat, a.dir, b.vec)
result
## Success: the objective function is 130000
result$solution
## [1] 10 30
Таким образом, максимальное значение целевой функции равно 130000 и оно достигается при x1 и x2 равными, соответственно: 10 и 30.
Поскольку пакет linprog является дополнением к предыдущему пакету, то переменные уже все инициализированы.
library(linprog)
## Warning: package 'linprog' was built under R version 3.2.2
(result<-solveLP( f.obj, b.vec, a.mat, TRUE,const.dir=a.dir,lpSolve=T))
##
##
## Results of Linear Programming / Linear Optimization
## (using lpSolve)
##
## Objective function (Maximum): 130000
##
## Solution
## opt
## A 10
## B 30
##
## Constraints
## actual dir bvec free
## 1 330 <= 330 0
## 2 280 <= 400 120
## 3 240 <= 240 0
## 4 10 >= 0 10
## 5 30 >= 12 18
Результат получился тот же, дополнительно выведена информация по свободным ресурсам. Таким образом,GNU R предоставляет достаточно удобный механизм для решения задач линейного программирования.
x1<- (-100:500)/10
old<-par(mar=c(1,1,1,1))
plot(0,type="n",xlab="",ylab="", xlim=c(-10, 50),ylim = c(-10, 50),bty="n",xaxt="n",yaxt="n")
polygon(c(0,0,10,20,22),c(12,33,30,20,12), col = "lightblue", border = NA)
axis(1,pos=c(0,0),at=c(-10,10,20,30,40))
axis(2,pos=c(0,0),las=2,at=c(-10,10,20,30,40))
arrows(-10.5,0,51,0,angle=15)
arrows(0,-10.5,0,51,angle=15)
lines(x1,(330-3*x1)/10,col="blue")
text(30,30,expression(3*х[1]+10*х[2]==330),cex=0.8,col="blue")
lines(x1,(400-16*x1)/4,col="red")
text(20,45,expression(16*х[1]+4*х[2]==400),cex=0.8,col="red")
lines(x1,(240-6*x1)/6,col="green")
text(8,40,expression(6*х[1]+6*х[2]==240),cex=0.8,col="green")
abline(h=12)
lines(x1,(-25*x1)/35,lty=3,lwd=3)
text(-5,5,expression(2500*х[1]+3500*х[2]==0),cex=0.8)
arrows(0,0,12.5,17.5)
lines(x1,(130000-2500*x1)/3500,lty=2,lwd=3)
text(35,20,expression(2500*х[1]+3500*х[2]==130000),cex=0.8)
points(10,30,cex=1.5,col="red",pch=19)
sessionInfo()
## R version 3.2.0 (2015-04-16)
## Platform: x86_64-w64-mingw32/x64 (64-bit)
## Running under: Windows 7 x64 (build 7601) Service Pack 1
##
## locale:
## [1] LC_COLLATE=Russian_Russia.1251 LC_CTYPE=Russian_Russia.1251
## [3] LC_MONETARY=Russian_Russia.1251 LC_NUMERIC=C
## [5] LC_TIME=Russian_Russia.1251
##
## attached base packages:
## [1] stats graphics grDevices utils datasets methods base
##
## other attached packages:
## [1] linprog_0.9-2 lpSolve_5.6.11
##
## loaded via a namespace (and not attached):
## [1] magrittr_1.5 formatR_1.2.1 tools_3.2.0 htmltools_0.2.6
## [5] yaml_2.1.13 stringi_0.4-1 rmarkdown_0.6.1 knitr_1.10.5
## [9] stringr_1.0.0 digest_0.6.8 evaluate_0.8