ВВЕДЕНИЕ
В МАТЕМАТИЧЕСКИЕ ВЫЧИСЛЕНИЯ
В СИСТЕМЕ MAPLE
(часть 5)
Тема 11 (продолжение). Реализация методов оптимизации
Транспортная задача
На прошлой лекции нами была рассмотрена постановка так называемой транспортной задачи. Была сформулирована, но не решена следующая сравнительно простая транспортная задача, условие которой приведем еще раз.
Задача
В трех хранилищах горючего ежедневно хранятся 20, 10 и 15 тонн горючего. Это горючее каждый день перевозят на четыре топливозаправочные станции в количествах, равных соответственно 10, 15, 10 и 10 тонн. Стоимости перевозок 1 тонны горючего из хранилищ к заправочным станциям задаются в виде стоимостной матрицы (в у.е.):
|
|
Заправочная станция |
|||
|
Хранилище |
1 |
2 |
3 |
4 |
|
1 |
9 |
7 |
5 |
3 |
|
2 |
1 |
2 |
4 |
6 |
|
3 |
8 |
10 |
12 |
1 |
Необходимо составить такой план перевозок горючего, при котором общая стоимость перевозок была бы минимальной.
Обратим внимание, что наша задача является сбалансированной (запасы горючего в хранилищах в точности совпадают с объемом потребления горючего на топливозаправочных станциях). Решим далее эту задачу, используя возможности системы Maple.
Зададим матрицу перевозок (x), матрицу стоимостей перевозок (C) и целевую функцию задачи (z).
> x:=matrix(3,4);
> # x – искомый план перевозок (задан в матричной форме)
> C:=matrix([[9,7,5,3],[1,2,4,6],[8,10,12,1]]);
> # C – матрица стоимостей перевозок (задана условиями задачи)
> z:=sum(sum(C[i,j]*x[i,j],i=1..3),j=1..4);
> # z – целевая функция задачи
> # далее решаем задачу линейного программирования
> with(simplex):
> c_limits:={sum(x[1,j],j=1..4)=20,
sum(x[2,j],j=1..4)=10,
sum(x[3,j],j=1..4)=15,
sum(x[i,1],i=1..3)=10,
sum(x[i,2],i=1..3)=15,
sum(x[i,3],i=1..3)=10,
sum(x[i,3],i=1..3)=10};
> # c_limits – набор ограничений задачи
> minimize(z,c_limits,NONNEGATIVE);
Матричный вид полученного решения:
> v:=matrix([[0,10,10,0],[5,5,0,0],[5,0,0,10]]);
Минимальная стоимость перевозок, соответствующая полученному плану перевозок (решению):
> st:=sum(sum(C[i,j]*v[i,j],i=1..3),j=1..4);
Итак, нами получен следующий ответ: минимальная стоимость перевозок составляет 185 у.е., ей соответствует следующий план перевозок:
Задачи целочисленного линейного программирования
Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Другими словами, задача целочисленного линейного программирования – это задача, где некоторые или все переменные должны принимать строго целочисленные значения, а целевая функция и ограничения – линейные. В некоторых задачах целочисленные значения могут быть равными только 0 или 1 и тогда такие задачи называются задачами с булевыми переменными.
Изучение данного раздела вызывается тем, что огромное количество прикладных (экономических, технических и т.д.) задач носит дискретный, чаще всего целочисленный характер, что связано, как правило, с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д.
Задача
линейного целочисленного программирования
формулируется следующим образом: найти
такое решение (план)
,
при котором целевая функция
принимает максимальное или минимальное
значение при ограничениях:
;
;
‑ целые
числа.
Следует
отметить, что некоторые задачи
транспортного типа «автоматически»
обеспечивают решение задачи в целых
числах (если, конечно, целочисленны
параметры условий). Однако в общем случае
условие целочисленности
,
добавляемое к обычным задачам линейного
программирования, может существенно
усложнить ее решение.
Для решения задач целочисленного линейного программирования используется ряд методов. Самый простой из них – обычный метод линейного программирования. В случае если компоненты оптимального решения оказываются нецелочисленными, их округляют до ближайших целых чисел. Этот метод применяется тогда, когда отдельная единица совокупности составляет малую часть объема всей совокупности. В противном случае округление может привести к далекому от оптимального целочисленному решению, поэтому используют специально разработанные методы.
Рассмотрим ряд специальных оптимизированных задач, сводящихся к задачам целочисленного линейного программирования. Одной из таких задач является задача о назначениях, с помощью которой можно получить ответ на вопросы типа: как распределить рабочих на станках, чтобы общая выработка была наибольшей или затраты на зарплату наименьшими; как наилучшим образом распределить экипажи самолетов; как назначить людей на различные должности (отсюда и название задачи) и т.д. и т.п.
Задача о назначениях
Задачу
о назначениях в общем виде может быть
сформулирована следующим образом. Имеем
n
исполнителей, которые могут выполнять
n
различных работ. Известна полезность
,
связанная с выполнением i-ым
исполнителем j-ой
работы
.
Требуется назначить исполнителей на
работы так, чтобы добиться максимальной
полезности, при условии, что каждый
исполнитель может быть назначен только
на одну работу и за каждой работой должен
быть закреплен только один исполнитель.
Математическая модель задачи примет вид:
Каждый исполнитель назначается только на одну работу:
.
На каждую работу назначается только один исполнитель:
.
Условия неотрицательности и целочисленности искомого решения:
.