ЛАБОРАТОРНАЯ РАБОТА № 9
СИСТЕМА КОМПЬЮТЕРНОЙ МАТЕМАТИКИ MAPLE.
ПОИСК ОПТИМАЛЬНЫХ РЕШЕНИЙ
Цель работы: приобрести практические навыки решения задач линейной и нелинейной оптимизации с помощью библиотек simplexиOptimization СКМ MAPLE.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Библиотека Simplex
Если требуется найти переменные, при которых линейная функция многих переменных имеет максимум (или минимум) при выполнении определенных ограничений, заданных в виде линейных равенств или неравенств, то следует использовать симплекс-метод. Этот метод реализован в библиотеке simplex, содержащей алгоритм линейной оптимизации.Библиотека simplex, как и любая другая, подключается командой with. Подробнее с функциями этой библиотеки можно ознакомиться в справочной системе СКМ Maple.
Поиск максимума (минимума) функции осуществляется командами maximize (minimize), которые используются в следующем формате:
maximize(expr, opt1, opt2,..., optn)
minimize(expr, opt1, opt2,..., optn)
здесь
expr - алгебраическое выражение,
opt1, opt2,..., optn – параметры оптимизации.
В качестве параметров оптимизации можно указывать в фигурных скобках ограничительную систему неравенств. Поскольку пакет simplex предназначен для решения задач линейной оптимизации, после его загрузки команды maximize и minimize меняют свое действие. Теперь эти команды выдают координаты точек, при которых заданная линейная функция имеет максимум или минимум. При этом допускается дополнительная опция для поиска только неотрицательных решений NONNEGATIVE.
Пример 9.1
При каких значениях переменных функция f(x,y,z)=-x+2y+3z имеет максимум, если требуется выполнение условий x+2y-3z<=4, 5x-6y+7z<=8, 9x+10z<=11, а все переменные неотрицательные?
Сеанс работы в Maple:
>restart: with(simplex);
>f:=-x+2*y+3*z; # Целевая функция
>ogran:={x+2*y-3*z<=4, 5*x-6*y+7*z<=8, 9*x+10*z<=11}: # Ограничения
>rez:=maximize(f, ogran, NONNEGATIVE); # Поиск решения в данном случае максимизация функции
СКМ MAPLE выдает ответ в самой точной форме – символьной, более точной, чем любой из численных методов. Однако, если желателен ответ в виде числа с плавающей точкой, то его можно найти в конце символьных вычислений. Для этой цели можно использовать функцию evalf(expr, n).
> rez:=evalf(rez,3);
Максимум функции при заданной системе ограничений можно определить с помощью функции subs(x=a, expr),которая подставит вычисленные значения переменных x, yи z(rez)в функцию f.
> F:=subs(rez,f);
Таким образом, максимальное значение, равное 10,6, в условиях заданной системы ограничений функция F принимает при значениях неизвестных x=0, y=3.65, z=1.1.
Библиотека Optimization
Этастандартная библиотекапозволяет отыскивать оптимальные решения для задач следующего вида:
· линейного программирования LPSolve;
· квадратического программирования QPSolve;
· нелинейного программирования NLPSolve;
· среднеквадратического отклонения LSSolve.
ПРАКТИЧЕСКАЯ ЧАСТЬ
Задание 1. Решить задачу линейного программирования, используя библиотеку simplex и библиотеку Optimization.
Фирма производит три вида продукции (A, B, C), для выпуска каждого требуется определенное время обработки на всех четырех устройствах.
| Вид продукции | Время обработки, ч. | Прибыль, у.е. | |||
| I | II | III | IV | ||
| A | |||||
| B | |||||
| C |
Рассчитать оптимальный план производства, если допустимое время работы на устройствах I, II, III, IV составляет соответственно 84, 42, 21 и 42 часа.
Экономико-математическая модель задачи имеет вид:
целевая функция: func:=3*A+6*B+4*C;
ограничения: 1∙А+6∙B+3∙C<=84
3∙A+1∙B+3∙C<=42
1∙A+3∙B+2∙C<=21
2∙A+3∙B+4∙C<=42
A,B,C – неотрицательные (> =0)
A,B,C – целочисленные.
Здесь A,B,C – количество производимой продукции каждого вида.
Приведем решение в системе Maple с использованием библиотеки simplex:
> func:=3*A+6*B+4*C;
> ogran:={1*A+6*B+3*C<=84, 3*A+1*B+3*C<=42, 1*A+3*B+2*C<=21, 2*A+3*B+4*C<=42};
> rez:=maximize(func, ogran, NONNEGATIVE);
> rez:=evalf(rez,3);
> F:=subs(rez,func);
Решение в системе Maple с использованием библиотеки Optimization:
>restart;
>with(Optimization);
[ImportMPS, Interactive, LPSolve, LSSolve, Maximize, Minimize, NLPSolve, QPSolve]
>func:=3*A+6*B+4*C;
3A+6B+4C
>ogran:={1*A+6*B+3*C<=84, 3*A+1*B+3*C<=42, 1*A+3*B+2*C<=21, 2*A+3*B+4*C<=42};
{1A+6B+3C<=84, 3A+1B+3C<=42, 1A+3B+2C<=21, 2A+3B+4C<=42};
>LPSolve(func, ogran, assume={nonnegative, integer},maximize);
[54., [A=12, B=3, C=0]]
Следует отметить, что библиотека simplex не предусматривает параметра для наложения ограничения целочисленности на переменные. Поэтому результаты оптимизации различаются. Таким образом, при необходимости получения целочисленного решения оптимизационных задач использование библиотеки Optimization предпочтительно.
Задание 2. Решить задачу нелинейного программирования, используя библиотеку Optimization.
Предприятие выпускает два вида продукции. Для изготовления продукции требуются ресурсы трех видов. С учетом брака расход ресурсов на единицу производимой продукции j-го вида определяется выражением aij+kij xj, а прибыль в зависимости от объемов производства равна рj+ ljxj, где
| xj– | искомый объем производства продукции j-го вида, |
| aij– | норма расхода i-го ресурса на производство единицы продукции j-го вида, |
| kij– | коэффициент изменения расхода соответствующего ресурса с учетом выпуска бракованных изделий, |
| рj- | прибыль от единицы продукции j-го вида, |
| lj – | коэффициент изменения прибыли, влияющий на объем производства продукции. |
Требуется найти такие объемы производства продукции, при которых прибыль максимальна.
Исходные данные к задаче приведены в таблице 9.1.
Таблица 9.1. Исходные данные
| Ресурс(i) | Запас ресурса | Норма расхода ресурсов aij на продукцию вида j | Коэффициент изменения норм расхода ресурсов kij на продукцию вида j | ||
| 0,1 | 0,05 | ||||
| 0,2 | 0,2 | ||||
| 0,1 | 0,15 | ||||
| Прибыль (ден. ед.) | |||||
| Коэффициент изменения прибыли | -0,08 | -0,1 |
Составим математическую модель задачи.
При заданных значениях параметров целевая функция имеет вид
f(x1,x2)=(100-0.8x1)x1+ (120-0.1x2)x2 à max,
или
f(x1,x2)=100x1-0.8x12+120x2-0.1x22 à max.
Ограничения по ресурсам имеют вид
(15+0.1x1)x1+(18+0.05x2)x2 ≤ 1350
(12+0.2x1)x1+(16+0.2x2)x2 ≤1400
(17+0.1x1)x1+(14+0.15x2)x2 ≤ 1580
или
15x1+0.1x12+18x2+0.05x22 ≤ 1350
12x1+0.2x12+16x2+0.2x22 ≤ 1400
17x1+0.1x12+14x2+0.15x22 ≤ 1580
X1 ≥ 0, x2 ≥ 0
Поскольку требуется рассчитать объемы производства продукции в усл. ед., ограничение целочисленности не накладывается.
Решение в системе Maple с использованием библиотеки Optimization:
>restart:with(Optimization);
>func:=100*x1-0.08*x1^2+120*x2-0.1*x2^2;
>ogran:={15*x1+0.1*x1^2+18*x2+0.05*x2^2<=1350,12*x1+0.2*x1^2+16*x2+0.2*x2^2<=1400, 17*x1+0.1*x1^2+14*x2+0.15*x2^2<=1580};
>rez:=NLPSolve(func,ogran,assume=nonnegative,maximize);
>rez:=evalf(rez,3);
Максимальная прибыль в размере 7220 ден. ед.будет получена при объеме производства продукции первого вида, составляющем 32,6 усл.ед, продукции второго вида 34,7 усл.ед.
Задания для самостоятельной работы 
Задание 1. Решить задачу линейного программирования, используя библиотеку simplex и библиотеку Optimization.
Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1 часов, оборудование второго типа – а2 часов, оборудование третьего типа – а3 часов. На производство единицы изделия В оборудование первого типа используется в1 часов, оборудование второго типа – в2 часов, оборудование третьего типа – в3 часов.
На изготовление всех изделий администрация предприятия может предоставить оборудование первого типа не более чем на t1 часов, оборудование второго типа не более чем на t2 часов, оборудование третьего типа – не более чем на t3 часов.
Прибыль от реализации единицы готового изделия А составляет α руб., а изделия В – β руб.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.
Варианты заданий приведены в таблице 9.2.
Таблица 9.2. Варианты заданий
| Вариант | а1 | а2 | а3 | в1 | в2 | в3 | t1 | t2 | t3 | α | β |
Задание 2. Решить задачу нелинейного программирования, используя библиотеку Optimization в соответствии с заданием, выданным преподавателем.