§ 5. Задачи с разрывной целевой функцией

5.1. Из задач этого типа наиболее важной и изученной является так называемая транспортная задача с фиксированными доплатами. Пусть, как в обычной транспортной задаче, через обозначены

пункты производства некоторого однородного груза, через пункты его потребления. Даны величины объем производства в пункте производства объем потребления в пункте потребления

Ищутся величины (объемы перевозок из пункта в пункт удовлетворяющие естественным транспортным ограничениям

и минимизирующие функцию

Каждое в (5.2) имеет вид

Числа естественно интерпретировать как затраты на перевозку единицы груза из Под можно подразумевать, например, плату за аренду транспортных средств, не зависящую от их загрузки, либо затраты на строительство магистрали от каждого пункта до каждого пункта не зависящие от будущих грузопотоков. Естественно считать все неотрицательными.

Задачу называют транспортной задачей с фиксированными доплатами, или неоднородной транспортной задачей. Ясно, что если все она превращается в обычную транспортную задачу. В противном же случае эта задача из-за разрывности каждого слагаемого (5.3) в нуле вообще выпадает из рамок линейного программирования; однако путем введения дополнительных целочисленных переменных ее удается свести к частично целочисленной задаче линейного программирования.

Способ такого сведения был указан Балинским [49]. Он состоит в следующем. Найдем величины

Рассмотрим задачу минимизации

при условиях (5.1) и дополнительном условии

Частично целочисленная задача (5.5), (5.1), (5.6) оказывается эквивалентной исходной задаче (5.1) -(5.3). Действительно, при в силу (5.6) автоматически будет и а при неравенства (5.6) становятся излишними, так как в любом допустимом плане транспортной задачи условия выполнены всегда. Наоборот, если в некотором оптимальном плане задачи (5.5), (5.1), (5.6) будет то соответствующее должно быть нулем (если оно окажется положительным, то план не будет оптимальным, ибо, уменьшив это мы не нарушим ограничений и придадим целевой функции (5.5) меньшее значение). Наконец, если то в силу условий может быть только единицей.

Таким образом, целочисленные переменные в этой постановке согласуют строительство магистралей между (или, в зависимости от интерпретации, аренду транспорта для этой магистрали) и осуществление перевозок между

Основанный на этом сведении приближенный метод решения транспортной задачи с фиксированными доплатами будет описан в § 1 гл. 16.

5.2. Рассмотрим теперь более общую модель с неоднородной разрывной целевой функцией. Ее удобно будет сформулировать в терминах, близких к задаче о смесях, хотя такая интерпретация не является единственно возможной. Обозначим через компоненты смеси, а через интересующие нас элементы в этих компонентах. Заданы следующие величины: содержание элемента в единице компоненты ограничения снизу на содержание каждого элемента в смеси,

стоимость закупки единицы компоненты фиксированная стоимость заказа компоненты не зависящая от заказываемого количества.

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

при условиях

где

Подчеркнем, что требование целочисленности на переменные не накладывается.

Эту задачу можно свести к общей частично целочисленной задаче линейного программирования посредством приема, описанного в п. 5.1. Предположим, что в дополнение к условиям (5.8) заданы еще верхние границы для переменных:

(или же эти границы могут быть определены из физической сущности задачи хотя бы грубым образом). Рассмотрим задачу минимизации

при условиях (5.8) и дополнительном условии

Эквивалентность частично целочисленной задачи (5.11), (5.8), (5.12) и исходной задачи устанавливается рассуждениями, совершенно аналогичными проведенным в п. 5.1; их можно предоставить читателю.

Отметим, что возможность сведения задач с разрывной целевой функцией к частично целочисленным базируется на наличии верхних границ для переменных. Этот прием вообще является характерным для целочисленного программирования; ср., например, построения, проводившиеся в § 4. В транспортной задаче эти границы определяются внутренним образом (см. (5.4)); в общей задаче их нужно постулировать или определять особым образом. В некоторых случаях границы вычисляются просто; например, если все то в качестве можно взять

где минимум берется по всем для которых