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



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


При заданных значениях х1, х2, ..., xn суммарный вес предметов, которые мы берем в машину, равен q1x1 + q2x2 + ... + qnxn. Условие ограниченной грузоподъемности запишется в виде неравенства:

q1x1

+ q2x2 +.... + qnxn

 Q.        (11.1)

Теперь запишем общую стоимость предметов, которую мы хотим максимизировать:

        (11.2)

Таким образом, задача на вид почти не отличается от обычной задачи линейного программирования: найти неотрицательные значения переменных х1, х2, ..., хn, которые удовлетворяют неравенству (11.1) и обращают в максимум линейную функцию этих переменных (11.2). На первый взгляд может показаться, что и решать ее надо как задачу линейного программирования, введя дополнительные ограничения-неравенства (каждый предмет — только один!):

x1

 1, x2
 1, …, xn
 1.

Ничуть не бывало! Найденное таким образом решение может оказаться не целым, а дробным, а значит неосуществимым (не можем же мы погрузить в машину треть рояля и половину шкафа!). Наша задача отличается от обычной задачи линейного программирования: она представляет собой задачу целочисленного программирования.

Вторая мысль, которая приходит в голову: а нельзя ли решить обычную задачу линейного программирования и округлить полученные значения хi до ближайшего из целых чисел 0 или 1? К сожалению, и так в общем случае поступать нельзя. Полученное таким образом решение даже может не удовлетворять ограничению (11.1), т. е. «не влезет» в данный вес Q. А если и «влезет», то может быть совсем не оптимальным. В отдельных случаях такое округление допустимо; например, если мы в задаче 3 § 7 получим ответ:

«производством ткани первого вида надо занять 185,3 станков первого типа», то, разумеется, мы без зазрения совести округлим это решение до 185. Если же идет речь о ресурсах неделимых (особо ценных или же уникальных), то задачу надо ставить как задачу целочисленного программирования.

Надо заметить, что вообще задачи целочисленного программирования гораздо труднее, чем обычные задачи линейного программирования.


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