рицательной ценой в 300, 200 и 300 единиц груза (см. таблицы 14-17; составляющие соответствующих циклов выделены жирным):

Таблица 14

перебрасывается 300:

Таблица 15

перебрасывается 200:

Таблица 16

перебрасывается 300:

Таблица 17

Замечание 2. Мы обсудили ситуацию, когда суммы заявок и запасов совпадают,

Однако так бывает нечасто:

1-й случай - сумма запасов больше суммы заявок,

/=1 *=1

2-й случай - сумма запасов меньше суммы заявок,

/=1 *=i

Тем не менее, оба эти несбалансированных случая можно свести к ситуации, рассмотренной выше. Покажем, как это можно сделать. Случай 1-й. Положим

и создадим виртуальный пункт назначения В +ь стоимость перевозки единицы груза в который из каждого пункта отправления равна нулю,

1.1*1 я О-

В результате мы получим сбалансированную транспортную задачу

/=1 к=1

с т(п + 1) числом неизвестных. Если значение х. +1 в оптимальном наборе положительно, это означает, что х. Л+1 единиц груза никуда не отправляются, а остаются в пункте At. Случай 2-й. Положим

*=i /=1

и создадим виртуальный пункт отправления Ат+1. Это позволит найти самую дешевую схему перевозок; правда, с удовлетворением заявок могут быть проблемы (справедливость их удовлетворения).

В результате получим сбалансированную транспортную задачу

м+1 п

/=1 *=i

с нулевой стоимостью перевозки ст+1гк.

И наконец обсудим

Реальный пример [10, с. 167-168]. Автобаза должна была регулярно доставлять строительные материалы на несколько стройплощадок города Москвы. Перед группой сотрудников вычислительного центра Академии наук СССР (описанные события относятся к 1960-1961 годам) была поставлена задача - рассчитать оптимальную схему поездок автомашин.

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

Выход из ситуации вполне очевиден: необходимо было доходчиво объяснить тресту, который управлял автобазами, что в его же интересах изменить систему показателей, по которым оценивалась бы работа отдельных автобаз. Это и было сделано, но много позже.

В теории линейного программирования есть и другие эффективные методы, позволяющие решать транспортные задачи [4], [7], [8], [11].

4.3. целочисленное программирование

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

Рассмотрим следующий пример.

Пример. Небольшая фирма производит два вида продукции: столы и стулья. Для изготовления одного стула требуется 3 фута древесины, а для изготовления одного стола - 7 футов. При этом на изготовление одного стула уходит 2 часа рабочего времени, а на изготовление стола -