Стратегия социально-экономического развития Омской области

- 85/7 Х₃  - 19800/7 Х₄  - 1800/7 Х₅  = F - 308571.

Поскольку все переменные неотрицательны, то из последнего уравнения  следует, что прибыль F достигает своего максимального значения, равного 308571, при Х₃  = Х₄  = Х₅  = 0. Из остальных уравнений следует, что при этом Х₁  = 120000/7 = 17143, Х₂  = 30000/7 = 4286, Х₆  = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено. 

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

Транспортная  задача.

Различные технико-экономические  и экономические задачи менеджмента, от оптимальной загрузки станка и  раскройки стального листа или  полотна ткани до анализа межотраслевого баланса и оценки темпов роста  экономики страны в целом, приводят к необходимости решения тех  или иных задач линейного программирования. В книге [1] приведен обширный перечень публикаций, посвященный многочисленным применениям линейного программирования в металлургии, угольной, химической, нефтяной, бумажной и прочих отраслях промышленности, в проблемах транспорта и связи, планирования производства, конструирования и хранения продукции, сельском хозяйстве, в научных исследованиях, в том числе экономических, и  даже при регулировании уличного движения. 

В качестве очередного примера  рассмотрим т.н. транспортную задачу. Имеются  склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить  товар со складов потребителям. Можно  по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю  и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному  потребителю. Требуется минимизировать издержки по перевозке. 

Например, может идти речь о перевозке песка - сырья для  производства кирпичей. В Москву песок  обычно доставляется самым дешевым  транспортом - водным. Поэтому в качестве складов можно рассматривать  порты, а в качестве запасов - их суточную пропускную способность. Потребителями  являются кирпичные заводы, а их потребности определяются суточным производством (в соответствии с  имеющимися заказами). Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным  правилам, на которых не имеет смысла останавливаться. Поэтому затраты  на доставку товара с определенного  склада тому или иному потребителю  можно считать известными.  

Рассмотрим пример транспортной задачи, исходные данные к которой  представлены в табл. 3. В ней, кроме  объемов потребностей и величин  запасов, приведены стоимости доставки единицы товара со склада i, i = 1,2,3, потребителю j, j = 1,2,3,4. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется 50+70 =120 единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.

Таблица 3.

Исходные данные к транспортной задаче.

Надо спланировать перевозки, т.е. выбрать объемы Х_ij  поставок товара со склада i потребителю j , где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:

X₁₁  + Х₁₂  + Х₁₃  + Х₁₄  = 60 ,

X₂₁  + Х₂₂  + Х₂₃  + Х₂₄  = 80 ,

X₃₁  + Х₃₂  + Х₃₃  + Х₃₄  = 60 .

Во-вторых, известны потребности  клиентов:

X₁₁  + Х₂₁ + Х₃₁   = 50 ,

X₁₂  + Х₂₂ + Х₃₂  = 40 ,

X₁₃  + Х₂₃ + Х₃₃   = 70 ,

X₁₄  + Х₂₄ + Х₃₄   = 40 .

Итак, всего 7 ограничений  типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений. 

Целевая функция - издержки по перевозке, которые необходимо минимизировать:

F = 2 X₁₁  + 5 Х₁₂  + 4 Х₁₃  + 5 Х₁₄  + X₂₁  + 2 Х₂₂  + Х₂₃  + 4 Х₂₄  +

+ +3 X₃₁  + Х₃₂  + 5 Х₃₃   + 2 Х₃₄  → min . 

Кроме обсуждаемой, рассматриваются  также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона. 

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