Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 64


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

При этом нужно иметь в виду, что все перевозки хiф, стоящие в правом столбце, фактически никуда не отправляются, а остаются на пунктах отправления Ai.

Может встретиться также случай   

(запасов не хватает для удовлетворения всех заявок);

в этом случае можно тем или другим способом «срезать» заявки и снова получить транспортную задачу с правильным балансом. Если нас совершенно не интересует, насколько «справедливо» удовлетворяются заявки, а важно только «подешевле развезти» имеющиеся запасы (все равно, куда), то можно ввести в рассмотрение фиктивный пункт отправления Аф, условно приписав ему недостающий запас, равный

Подробнее на этих вопросах мы останавливаться не будем (см. [6]).

§ 11. Задачи целочисленного программирования. Понятие о нелинейном программировании

На практике часто встречаются задачи, совпадающие по постановке с задачами линейного программирования, по отличающиеся тон особенностью, что искомые значения переменных непременно должны быть целым и. Такие задачи называются задачами целочисленного программирования; дополнительное условие целочисленности переменных существенно затрудняет их решение.

Рассмотрим пример такой задачи. Пусть имеется ряд предметов (ценностей) П1, П2, … Пn, которые желательно увезти из угрожаемого района. Известны стоимости этих предметов: с1, с2, ..., сn и их веса q1, q2, …, qn Количество и вид предметов, которые мы можем увезти, лимитируется грузоподъемностью Q машины. Требуется из всего набора предметов выбрать наиболее ценный набор (с максимальной суммарной стоимостью предметов), вес которого укладывается в Q.

Введем в рассмотрение переменные х1, х2, ..., xn, определяемые условием: xi =1, если мы берём в машину предмет Пi и xi = 0,— если не берем.




Содержание  Назад  Вперед