Задача о защите поверхности

Мы уже рассматривали решение этой задачи методом динамического программирования (разд. 2.5.5).

Если су — затраты при защите i-ro элемента поверхности j-м способом, то целевая функция имеет вид

где ху =1, если на i-м элементе используется j-й способ защиты, и Ху = 0 в противном случае. Здесь (i = 1, 2, ..., m и j = 1,2, ..., n).

где суммарные потери от неполной защиты поверхности Dmax и соответственно потери на i-м элементе при его защите j-м способом dy заданные величины.

Нужно еще условие:

Это условие означает, что на каждом элементе используется только один способ защиты. И, конечно, нужны неравенства

О < Ху< 1.

Это снова задача целочисленного линейного програмирования. Однако рассчитывать на то, что целочисленные значения переменных будут получаться автоматически, не приходится. При большой размерности задачи динамическое программирование заведомо более эффективно, чем применение специальных методов целочисленного программирования.

Задача о размещении оборудования

Предположим, что есть п объектов, которые нужно разместить на некотором транспортном средстве (например, приборы на самолете, на космическом корабле, грузы на товарном поезде, автомобиле и т. д.) Все объекты разместить нельзя из-за ограниченности грузоподъемности, габаритов или других ресурсов. Каждый объект с номером i имеет известный вес, габарит или иной показатель ay, по каждому из которых и ставится суммарное ограничение bj. Кроме того, известна оценка полезности каждого объекта. Задача состоит в том, чтобы, не превышая имеющиеся ресурсы (грузоподъемность, объем и т. д.), разместить такие объекты, чтобы их суммарная полезность была максимальна. Эта задача также сводится к линейному программированию.

Пусть xj = 1, если i-й объект будет размещен, и 0 в противном случае, i = 1, 2, ..., п. Пусть далее сх мера полезности i-ro объекта. Задача запишется в следующем виде. Найти

Таких неравенств столько, сколько показателей, по которым имеются ограничения. Вместо условия равенства х4 нулю или единице приходится ставить ограничения 0 < Xj< 1 (i = 1, 2, ..., n).

Это тоже задача целочисленного линейного программирования, но автоматически целочисленные решения могут и не получаться. Округление получающихся дробей имеет мало смысла не только из-за потери оптимальности, но и из-за нарушения ограничений. Поэтому и для данной задачи более эффективно применение метода динамического программирования при небольшом числе ограничений. В этом случае каждый показатель, по которому имеется ограничение, должен рассматриваться как ресурс, и задача сводится к оптимальному распределению ресурсов. Наличие только двух значений для щ существенно упрощает задачу, но при большом числе ограничений вычислительные трудности значительны [3].

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >