Краткие теоретические сведения. Данная задача является задачей поиска наилучшего варианта из трех имеющихся способов размещения дополнительного производства объемом S=b1+b2+b3+b4-d4

Данная задача является задачей поиска наилучшего варианта из трех имеющихся способов размещения дополнительного производства объемом S=b₁+b₂+b₃+b₄-d₄, в одном из пунктов: А₁, А₂, А₃. Введём в рассмотрение три переменные y₁, y₂, y₃, принимающие значения 0 или 1(переменные, обладающие таким свойством, называются булевскими) такие, что y_i=1 тогда и только тогда, когда дополнительное производство будет размещено в пункте A_i, где . Тогда задача сводится к задаче целочисленного линейного программирования. Тот факт, что дополнительное производство будет размещено, только в одном из пунктов математически запишется в виде системы ограничений:

y₁+ y₂+ y₃=1;

0£ y₁£1; 0£ y₂£1; 0£ y₃£1;

у₁,у₂,у₃ – целые.

При этом затраты на размещение дополнительного производства составят величину: y₁×h₁+ y₂×h₂+ y₃×h₃ (в последней сумме только одно слагаемое отлично от 0). С учетом транспортных затрат целевая функция для данной задачи имеет вид:

z=c₁×x₁+ c₂×x₂+ c₃×x₃+ c₄×x₄+ c₅×x₅+ c₆×x₆+ y₁×h₁+ y₂×h₂+ y₃×h₃,

где x_i- величина транспортного потока перевозок продукта по дуге i, c_i- коэффициент удельных транспортных расходов при перевозках по данной магистрали. Система неравенств материального баланса для производства и потребления и потоков перевозок для каждого населенного пункта имеет вид:

b₁+x₅+x₂£ x₁+x₄+y₁×S - для пункта А₁;

b₂+x₃+x₁£ x₂+y₂×S - для пункта А₂;

b₃+x₆ £ x₅+y₃×S - для пункта А₃;

b₄+x₄ £ x₃+x₆+d₄- для пункта А₄.

В левой части неравенств записываем объём потребляемой и вывозимой продукции, а в правой - объём ввозимой и возможно производимой продукции (для пункта А₄объём ввозимой и производимой продукции).

Таким образом, изучаемая задача сводится целочисленной задаче линейного программирования на поиск минимума:

z=c₁×x₁+ c₂×x₂+ c₃×x₃+ c₄×x₄+ c₅×x₅+ c₆×x₆+ y₁×h₁+ y₂×h₂+ y₃×h₃®min;