Пример 1. Решение задачи линейного программирования
Рассмотрим следующую задачу линейного программирования.
Предположим, что на мебельной фабрике из стандартных листов фанеры необходимо вырезать заготовки трех видов в количестве, соответственно равных 24, 31 и 18 штук. Каждый лист фанеры может быть разрезан на заготовки двумя способами. Количество получаемых заготовок при данном способе разрезания приведено в таблице.
В ней же указаны величины отходов, которые получаются при данном способе раскроя одного листа фанеры.
Таблица 1. Количество заготовок
|
Вид заготовки |
Количество заготовок (штук) при разрезании по каждому из способов |
|
|
|
1-ый способ |
2-ой способ |
|
1 |
2 |
6 |
|
2 |
5 |
4 |
|
3 |
2 |
3 |
|
Величина отходов (в м2) |
12 |
16 |
Необходимо определить, сколько листов фанеры и каким способом нужно раскроить так, чтобы было получено не менее требуемого числа заготовок при минимальных отходах.
В математической записи поставленная задача имеет вид:
целевая функция
,
где
f – отходы (м2);
x - количество листов фанеры, которые необходимо раскроить по первому способу;
y - количество листов фанеры, которые необходимо раскроить по второму способу;
ограничения:
Решить поставленную задачу в системе Maple можно с помощью команды minimize. Присваиваем переменной f выражение нашей функции f=12*х+16*у, а переменной c - систему ограничений {2*x+6*y>=24,5*x+4*y>=31,2*x+3*y>=18}. Предварительно подключив библиотеку simplex, обратимся к команде minimize(f,c). В результате получили решение х=3, т.е. три листа нужно раскроить первым способом, у=4 - четыре листа нужно раскроить вторым способом, f=100- минимальное значение отходов:
> restart:
> with(simplex):
> f:=12*x+16*y;
> c:={x>=0,y>=0,2*x+6*y>=24,5*x+4*y>=31,2*x+3*y>=18};
> minimize(f,c);
Пример 2. Решение задачи линейного программирования (получение дешевого металлургического сплава)
В металлургический цех в качестве сырья поступает латунь (сплав меди с цинком) четырех типов с содержанием цинка 10, 20, 25 и 40 % по цене 10, 30, 40 и 60 у.е. за 1 кг соответственно. В каких пропорциях следует переплавлять это сырье в цехе, чтобы получить сплав (латунь), содержащий 30 % цинка и при этом самый дешевый ?
Решение
Обозначим через
массу (в кг) j-го типа сырья, которое
используется для получения 1 кг требуемого
сплава. Тогда поставленную задачу можно
формализовать следующим образом:
Здесь функция
является целевой функцией нашей задачи.
Точное решение задачи
=(1/3, 0, 0, 2/3)
может быть найдено аналитически,
например, методом полного перебора всех
возможных вершин (соответствующего
графа состояний).
Итак, самым дешевым является сплав первого и четвертого типа сырья в отношении 1:2.
В результате получаем решение:
=0.3333,
=0,
=0,
=0.6667,
f=43.333333.
В системе Maple решаем данную задачу, используя команду minimize(f,c,vartype).
> restart:
> with(simplex):
> f:=10*x1+30*x2+40*x3+60*x4;
> c:={10*x1+20*x2+25*x3+40*x4=30,x1+x2+x3+x4=1,x1>=0,x2>=0,x3>=0,x4>=0};
> minimize(f,c);
Преобразуем выражение f в отдельную процедуру с целью последующего использования в вычислениях:
> fqproc:=codegen[makeproc](f,[x1,x2,x3,x4]);
> x1:=1/3; x2:=0; x3:=0; x4:=2/3;
> f_min:=fqproc(x1,x2,x3,x4); evalf(%);
