г) Задача о загрузке транспорта

Пусть имеется транспортная единица грузоподъемностью b, которую необходимо загрузить различными предметами x_j в разных количествах, причем c_j - стоимость; w_j - вес отдельного предмета j-го типа. Например, загружаются автомобили, тракторы, самолеты. Требуется определить оптимальную загрузку так, чтобы стоимость перевозимого груза была минимальной.

Очевидно, что стоимость всего перевозимого груза задается формулой

Необходимо найти такие целые числа x_j (j = 1,..., n), при которых эта линейная форма приняла бы максимальное значение при условиях

В отличие от предыдущих в этой задаче число ограничений i = 1. Она существенно отличается от ранее рассмотренных тем, что в ней искомые значения -величин x_i - целочисленные. Поэтому ее можно отнести к задачам целочисленного линейного программирования, которые решаются различными способами, рассмотренными в гл. 18, в том числе и с помощью динамического программирования.