ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
ВВЕДЕНИЕ
В МАТЕМАТИЧЕСКИЕ ВЫЧИСЛЕНИЯ
В СИСТЕМЕ 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-ой работы 
. Требуется назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.
|
|
|
Математическая модель задачи примет вид:
Каждый исполнитель назначается только на одну работу:
.
На каждую работу назначается только один исполнитель:
.
Условия неотрицательности и целочисленности искомого решения:
.
Задача о рюкзаке
Контейнер оборудован m отсеками вместимостью 
, для перевозки n видов продукции 
. Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0,1,2,... единиц. Пусть 
- расход i-ого отсека для перевозки единицы j-ой продукции. Обозначим через 
полезность единицы j-ой продукции. Требуется найти решение (план) перевозки, при котором максимизируется общая полезность набора видов продукции (это целевая функция задачи), загружаемых в контейнер.
Математическая модель задачи имеет вид:
,
при ограничениях на вместимости отсеков:
,
при условиях неотрицательности решения:
,
при условии целочисленности решения:
- целые числа 
.
Когда для перевозки используется только один отсек и каждый вид продукции может быть или взят или нет, то модель задачи примет следующий вид:
,
, 
.
Задача о коммивояжере
Коммивояжер должен посетить один и только один раз каждый из n городов, после чего вернуться в исходный пункт. Его маршрут должен при этом минимизировать суммарную длину пройденного пути.
Итак, математическая задача коммивояжера состоит в том, чтобы разработать такой маршрут обхода всех городов, для которого суммарная длина пройденного пути была бы минимальна.
Пусть cij – длина перехода из i-ого города в j-ый город, а xij - матрица переходов со следующими значениями:
xij = 1, если коммивояжер совершает переход из i-ого города в j-ый город;
xij = 0, если переход из i-ого города в j-ый город не совершается,
где i, j = 1.. n и i ¹ j.
Математическая модель задачи может быть представлена в следующем виде:
,
,
.
Последние два условия означают, что коммивояжер из каждого города выезжает только один раз и только один раз въезжает в каждый город.
Условия неотрицательности и целочисленности
.
В формулировке задачи учтено условие прохождения маршрута по 1 разу через все из n городов, т.е. так называемое условие цикличности (иначе маршрут представляет собой просто замкнутую ломаную без самопересечений в городах-точках).
К задачам целочисленного линейного программирования приводят также многие оптимальные задачи теории расписаний, в которой рассматриваются методы оптимизации оперативно-календарного планирования. В качестве примера таких задач можно привести задачу определения оптимальной очередности обработки изделий на различных станках или других рабочих местах, задачу составления программы «диспетчер» для управления работой ЭВМ в мультипрограммном режиме и т.п.
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Динамическое программирование (ДП) определяет оптимальное решение n-мерной детерминированной (т.е. дискретной) задачи путем ее декомпозиции на n этапов, каждый из которых представляет собой подзадачу относительно одной переменной. Вычислительное преимущество такого подхода состоит в том, что мы занимаемся решением одномерных оптимизационных задач подзадач вместо большой n-мерной задачи.
Фундаментальным принципом ДП, составляющим основу декомпозиции задачи на этапы, является оптимальность.
(Более детально с методом ДП и соответствующими алгоритмами решения задач ДП можно ознакомиться по следующей книге: Вентцель Е.С. Исследование операций: задачи, принципы, методология. Москва, Изд-во «Дрофа», 2004 г.; стр.84-111)
Дата добавления: 2022-06-11; просмотров: 23; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!