Linear Programming Output summary 10 страница

4.5.2. Изменения, влияющие на оптимальность решения

В этом разделе рассмотрим два фактора, которые могут изменить оптималь­ность текущего решения.

1. Изменение коэффициентов целевой функции.

2. Добавление в модель нового вида производственной деятельности (т.е. добав­ление новой переменной).

Изменение коэффициентов целевой функции. Эти изменения влияют только на оптимальность решения. Для определения влияния изменений коэффициентов це­левой функции следует пересчитать коэффициенты в z-строке только для небазис­ных переменных, поскольку для базисных переменных эти коэффициенты всегда остаются равными нулю.

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

1. С использованием методов 1 и 2 из раздела 4.2.3 вычисляются значения двойственных переменных.

2. На основе значений двойственных переменных по формуле 2 из раздела 4.2.4 вычисляются коэффициенты z-строки.

При этом возможны два варианта.

1. Если для новой z-строки условие оптимальности выполняется, текущее реше­ние остается оптимальным, но значение целевой функции может измениться.

2. Если условие оптимальности не выполняется, следует применить прямой симплекс-метод для получения нового оптимального решения.

Пример 4.5.4

Предположим, что фабрика игрушек TOYCO проводит новую ценовую политику относительно своих изделий. В соответствии с этим доход от одной модели поезда, грузовика и легкового автомобиля составляет соответственно 2, 3 и 4 долл. Получа­ем новую целевую функцию для этой модели

максимизировать z = 2х_х + Зх_г + Ах_г

Таким образом,

новые коэффициенты при базисных переменныхх₂, х₃ их, = (3, 4, 0).

По формулам метода 1 из раздела 4.2.3 вычислим значения двойственных пере­менных.

⁽ \_ 2

(Л.^.Л) =(ЗЛ0)

о

³-Л,о

2 4

Коэффициенты z-строки вычисляются как разности между значениями левых и правых частей ограничений двойственной задачи (формула 2 из раздела 4.2.4). Напомним, что эти коэффициенты пересчитываются только для небазисных ко­эффициентов, поскольку для базисных переменных они всегда остаются равны­ми нулю (проверьте!).

Глава 4. Двойственность и анализ чувствительности

„ 3 J5] _п „ 13 у, +3у, + Уз - 2 = — + 31-1 + 0-2 =—,

„ 3 хл у, - 0 = -.

Отметим, что здесь использовалось новое значение 2 коэффициента при перемен­ной х_х в выражении целевой функции.

Вычисления показывают, что текущее решение х_х — 0, х₂ = 100 и х_г = 230 остается оптимальным. Новое значение целевой функции равно 2x0+ 3x100 + + 4x230 = 1220 долл.

Предположим, что в рассматриваемой задаче целевая функция имеет следующий вид.

Максимизировать z = бд:, + Зд:₂ + 4х₃.

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

Базис	Х1	Хг	Хз	х4	х5	Хб	Решение
z	-3/4			3/2	5/4
хг	-1/4			1/2	-1/4
хз	3/2				1/2
х6				-2

Для нахождения нового оптимального решения следует ввести в базис переменную x_t и исключить из него переменную х₆. В результате получим решение х, — 10, х₂ = 102,5, дг₃ = 215 и z = 1227,50 долл. (проверьте!).

УПРАЖНЕНИЯ 4.5.4

1. Проверьте оптимальность решения задачи о фабрике TOYCO для следующих целевых функций. Если решение неоптимально, найдите новое оптимальное решение. (Симилекс-таблица с оптимальным решением для данной задачи представлена в начале раздела 4.5.)

a) 2 = 2x, + х₂ + 4х₃,

b) 2 = Зх, + 6д;₂ + х_ъ,

c) z = 8Xj + Зд:₂ + 9х₃.

2. Проверьте оптимальность решения задачи о компании Reddy Mikks (пример 4.3.1) для следующих целевых функций. Если решение неопти­мально, найдите новое оптимальное решение. (Симплекс-таблица с опти­мальным решением для данной задачи представлена в примере 3.3.1.)

a) г = Зд^ + 2д:₂,

b) 2 = 8х, + 10х₂,

c) z = 2х_х + 5х₂.

4.5. Анализ чувствительности оптимального решения

3. В упражнении 4.5.2.4 с помощью программы TORA вычислите оптимальное решение. На основе анализа чувствительности найдите оптимальное решение для следующих целевых функций.

а)		= 40л:,	+ 22л:2 + 45л:3,
Ь)		= 70л;,	+ 22л;2 + 45л:3,
с)		= 24л:,	+ 10л:2 + 45л:3,
d)		= 24л:,	+ 20л;2 + 45л:3,
е)		= 24л;, + 22л;2 + 50л:3,
f)		= 24л;,	+ 22л;2 + 40л;3.

Интервалы оптимальности для коэффициентов целевой функции. Другой путь исследования влияния коэффициентов целевой функции на оптимальность реше­ния заключается в вычислении (по отдельности) интервалов изменения каждого коэффициента, сохраняющих оптимальность текущего решения. Для этого следует заменить текущий коэффициент выражением с\ + d., где d_J — величина (положительная или отрицательная) изменения коэффициента с_г

Пример 4.5.5

В задаче о фабрике TOYCO запишем целевую функцию следующим образом.

Максимизировать z = (3 + d_l)x_i + 2х₂ + 5х₃. Найдем интервал оптимальности для изменения d_r

Мы должны следовать той же процедуре, которая описана выше. Но так как перемен­ная л:, не входит в оптимальный базис, значения двойственных переменных не изменят­ся и останутся такими же, как в исходной задаче (т.е. у, = 1, у₂ = 2, у₃ = 0). Более того, поскольку переменная лг, небазисная, то в 2-строке изменится только ее коэффициент, а все остальные коэффициенты останутся неизменными (почему?). Это означает, что нам необходимо применить формулу 2 из раздела 4.2.4 только к ограничению двой­ственной задачи, соответствующего переменной лг,.

л-,: у, + Зу₂ + у₃ - (3 + d_t) = 1 + 3x2 + 0 - (3 + dJ = 4 - d_v

Поскольку рассматривается задача максимизации, исходное решение будет оптималь­ным до тех пор, пока выполняется неравенство 4-с/,>0 или с/,<4. Это эквивалентно утверждению, что текущее решение останется оптимальным до тех пор, пока в целе­вой функции коэффициент при лг, не превысит величины 3 + 4 = 7.

Теперь рассмотрим изменение d₂ коэффициента при переменной л:₂ в выражении це­левой функции:

максимизировать z = Зл-, + (2 + d₂)x₂ + 5лг₃.

Различие здесь по сравнению с предыдущем случаем заключается в том, что пере­менная л:₂ входит в оптимальный базис, и поэтому изменение ее коэффициента из­менит значения двойственных переменных и, следовательно, значения коэффици­ентов в 2-строке, соответствующих всем небазисным переменным (напомним, что коэффициенты в 2-строке, соответствующие базисным переменным, останутся рав­ными нулю независимо от изменения целевой функции). Используя метод 1 из разде­ла 4.2.3, вычисляем значения двойственных переменных:

Глава 4. Двойственность и анализ чувствительности

1 -1 О

2 4

(УрУ₂.л) = (2 + «/,,5,0)

О

- О 2

1 1

-2

Теперь можно вычислить коэффициенты в 2-строке для небазисных переменных.

Из этих неравенств имеем d₂ < 16, d₂ > -2 и d₂ < 8 или

-2<rf₂<8.

Отсюда получаем интервал оптимальности для коэффициента с₂ = 2 + d₂:

0<с₂<10.

УПРАЖНЕНИЯ 4.5.5

1. Пусть в задаче о' фабрике TOYCO доход от одной модели легкового автомоби­ля составляет 5 + d₃ долл. Определите интервал для величины d₃, сохраняю­щий текущее оптимальное решение.

2. В задаче о фабрике TOYCO, используя решения из примера 4.5.5 и предыдущего упражнения, укажите, будет ли текущее решение оптимальным для следующих (независимых) ситуаций. Если решение изменится, найдите новое.

a) Доход от одной модели поезда возрос от 3 до 5 долл. До 8 долл.

b) Доход от одной модели поезда уменьшился от 3 до 2 долл.

c) Доход от одной модели грузовика увеличился от 2 до 6 долл.

d) Доход от одной модели легкового автомобиля уменьшился от 5 до 2 долл.

3. Пусть в задаче о компании Reddy Mikks коэффициенты целевой функции претерпели следующие изменения (каждое изменение рассматривается как отдельная задача).

a) Доход от одной тонны краски для наружных работ составляет 5 + rf, тыс. долл.

b) Доход от одной тонны краски для внутренних работ составляет 4 + d₂ тыс. долл.

Изменения d_x и d₂ могут быть как положительными, так и отрицательными. Применяя подходящее условие оптимальности к коэффициентам 2-строки оптимальной симплекс-таблицы, определите интервалы для величин и d₂, сохраняющие текущее оптимальное решение.

4.5. Анализ чувствительности оптимального решения

4. В задаче о компании Reddy Mikks, используя решение из предыдущего уп­ражнения, покажите, будет ли текущее решение оптимальным для следую­щих (независимых) ситуаций. Если решение изменится, найдите новое.

a) Доход от одной тонны краски для наружных работ возрос от 5 до 7 тыс. долл. Уменьшился от 5 до 4 тыс. долл.

b) Доход от одной тонны краски для внутренних работ возрос от 4 до 6 тыс. долл. Уменьшился от 4 до 3 тыс. долл.

5. Вернитесь к задаче из упражнения 4.5.2.5.

a) Найдите оптимальное решение с помощью программы TORA.

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

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

d) Вычислите новое оптимальное решение, если удельный доход от первой модели возрастет до 6 долл.

e) Найдите новое оптимальное решение при изменении удельного дохода от второй модели до 1 долл.

6. Вернитесь к задаче из упражнения 4.5.2.6.

a) Найдите оптимальное решение с помощью программы TORA.

b) Каков наименьший удельный доход от первого продукта, сохраняющий текущее оптимальное решение?

c) Найдите новое оптимальное решение при возрастании удельного дохода от первого продукта до 25 долл.

7. Пусть в задаче о фабрике TOYCO изменения d,, d₂ и d₃ производятся одно­временно.

a) Найдите условия, сохраняющие текущее решение оптимальным.

b) Используя условия, полученные в предыдущем пункте, найдите новое решение (если текущее изменилось) для следующих целевых функций.

i) 2 = 2х_{ + х₂ + 4at₃,

ii) 2 = Зд:, + 6х₂ + х_ъ,

iii) 2 = 8дг, + Зх₂ + 9дг₃.

8. Пусть в упражнении 3 изменения d, и d₂ производятся одновременно.

a) Найдите условия, сохраняющие текущее решение оптимальным.

b) Используя условия, полученные в предыдущем пункте, найдите новое решение (если текущее изменилось) для следующих целевых функций.

i) 2 = Зх, + 2х₂,

ii) 2 = Зх, + 9х₂,

iii) 2 = 5Xj + 5д:₂.

9. Вернитесь к задаче из упражнения 4.5.2.5.

a) Определите условия, сохраняющие текущее оптимальное решение при од­новременном изменении удельных доходов от обеих моделей устройств.

b) Найдите новое оптимальное решение, если целевая функция примет вид 2 = 5Xj + 2д:₂.

Глава 4. Двойственность и анализ чувствительности

10. Достаточное правило оптимальности. Правило, подобное достаточному правилу допустимости из упражнения 4.5.2.7, можно сформулировать и для проверки оптимальности текущего решения при одновременном изме­нении всех коэффициентов c_j целевой функции. Для этого представим коэф­фициенты c_j в виде c_j + d_r j = 1, 2, п. Предположим, что для всех измене­ний dj независимо получены индивидуальные интервалы u.<d_t< v_} значений, сохраняющих оптимальность текущего решения (как в примере 4.5.5). Оче­видно, что ц^<0 (v_}>0), поскольку эта величина соответствует максимально возможному уменьшению (увеличению) коэффициента c_jt сохраняющего те­кущее оптимальное решение. Для d_f, которые находятся в интервале Uj<di< у, определим отношение г. = djv. или r_j = dju^ в зависимости от того, будет величина d. положительной или отрицательной. По определению 0<г_у<1. Правило гласит, что достаточным (но не необходимым) условием сохранения оптимальности текущего решения является выполнение нера­венства г, + г₂ +... + r_n < 1. Если это неравенство не выполняется, то текущее решение может быть как оптимальным, так и неоптимальным. Это правило не применимо, если величины d_} выходят за свои интервалы оптимальности.

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

11. Покажите, что достаточное правило оптимальности (упражнение 10) явля­ется следствием неравенств z_j-c_j >0 в задаче максимизации и неравенств z_j - с. < 0 в задаче минимизации.

Добавление в модель ЛП нового вида производственной деятельности. Введение в модель линейного программирования нового вида производственной деятельности эквивалентно добавлению новой переменной в задачу ЛП. Добавление нового вида производственной деятельности интуитивно обосновано только в том случае, если эта деятельность экономически рентабельна, т.е. улучшает оптимальное значение целе­вой функции. Это условие можно проверить, применив к новой переменной форму­лу 2 из раздела 4.2.4, Поскольку новая переменная пока не является частью реше­ния, ее можно считать небазисной переменной. Тогда значения двойственных переменных, ассоциированных с текущим решением, останутся неизменными.

Если формула 2 показывает, что новая переменная удовлетворяет условию оп­тимальности, то это означает, что новая деятельность нежелательна, поскольку не улучшает оптимального решения. В противном случае новый вид деятельности яв­ляется рентабельным, и соответствующая ему переменная должна быть включена в базисное решение.

Пример 4.5.6

Оптимальное решение задачи ЛП о фабрике игрушек TOYCO показывает, что производство моделей поездов нерентабельно. Поэтому фабрика планирует заме­нить производство этих моделей выпуском модели пожарной машины, причем ее сборка будет осуществляться с использованием тех же производственных мощно­стей. Доход от новой игрушки ожидается в 4 долл. за одну модель. Ее время

4.5. Анализ чувствительности оптимального решения

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

Обозначим через х₇ объем производства новой продукции. Имея значения перемен­ных двойственной задачи (y_v у₂, у_ъ) = (1, 2, 0), вычисляем приведенную стоимость для переменной х₇:

1у, + 1у₂ + 2у₃ - 4 = 1 х 1 + 1 х 2 + 2 х 0 - 4 = -1.

Полученный результат показывает, что экономически целесообразно включить пе­ременную х₇ в оптимальное базисное решение. Чтобы найти новое оптимальное ре­шение, сначала с помощью формулы 1 из раздела 4.2.4 вычислим столбец коэффи­циентов ограничений, соответствующий переменной х₇.

(1	1 4		(1)		rn
,-2	2 1	К	,2J		1 2

Отсюда следует, что текущая симплекс-таблица должна быть приведена к следую­щему виду.

Базис	Х1	х2	х3	х7	х4	Хъ	Хб	Решение
z				-1
Х2	-1/4			1/4	1/2	-1/4
хз	3/2			1/2		1/2
Хб					-2

Теперь новое оптимальное решение можно найти, введя в базис переменную х₇ и исключив из него переменную л:₆. Новое решение составляют х_х = 0, х₂ = 0, х₂ = 125, х₇ = 210 и 2 = 1465 долл. (проверьте!).

Введение в модель ЛП нового вида деятельности, как следует из приведенного выше, можно рассматривать как обобщение ситуации, когда происходит измене­ние ресурсов, используемых для существующей деятельности. Например, в по­следнем примере можно считать, что переменная х₇ в исходной задаче имела нуле­вой коэффициент в целевой функции и нулевые коэффициенты в ограничениях на использование ресурсов. Но затем были изменены ее нулевой коэффициент в целе­вой функции и соответствующие нулевые коэффициенты в ограничениях. Поэтому введение в модель ЛП нового вида деятельности можно рассматривать как измене­ние параметров существующего вида деятельности.

УПРАЖНЕНИЯ 4.5.6

1. В исходной модели фабрики игрушек TOYCO производство моделей поездов не входит в оптимальный производственный план. Ситуация на рынке игру­шек не позволяет увеличить отпускную цену этих моделей. Поэтому фабрика решила усовершенствовать сборочные операции данной модели. Это привело к уменьшению времени выполнения каждой из трех сборочных операций на р%. Найдите значение р, при котором выпуск моделей поездов становится

Глава 4. Двойственность и анализ чувствительности

рентабельным. (Симплекс-таблица с оптимальным решением данной задачи приведена в начале раздела 4.5.)

2. Предположим, что в исходной модели фабрики игрушек TOYCO время вы­полнения трех сборочных операций при производстве моделей поездов уменьшено соответственно до 0,5, 1 и 0,5 минут. Доход от модели этого вида остался неизменным на уровне 3 долл. за одну игрушку. Найдите новое оп­тимальное решение.

3. Пусть производство модели нового вида (модель пожарной машины) требует соответственно 1, 2 и 3 минуты для выполнения каждой сборочной операции. Найдите оптимальное решение, если доход от одной модели нового вида со­ставляет а) 5 долл., Ь) 10 долл.

4. Вернитесь к модели компании Reddy Mikks (модель представлена в примере 4.3.1, симплекс-таблица с ее оптимальным решением— в примере 3.3.1). Предположим, что компания рассматривает возможность производства де­шевой краски для наружных работ, причем для производства тонны такой краски требуется 0,75 тонны сырья Ml и столько же сырья М2. Ситуация на рынке показывает, что производство краски для внутренних работ не должно превышать ежедневного производства обоих видов красок для наружных работ более чем на одну тонну. Доход от одной тонны новой краски составляет 3500 долл. Найдите новое оптимальное решение.

ЛИТЕРАТУРА

1. BazaraaM., Jarvis J., SheraliM. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.

2. Bradley S., Hax A., Magnanti T. Applied Mathematical Programming, Addison-Wesley, Reading, MA, 1977.

3. Nering E., Tucker A. Linear Programming and Related Problems, Academic Press, Boston, 1992.

Литература, добавленная при переводе

1. Ашманов С. А. Линейное программирование. — М.: Наука, 1981.

2. Гольштейн Е. Г. Теория двойственности в математическом программирова­нии и ее приложения. — М.: Наука, 1971.

3. Гольштейн Е. Г., Юдин Д. Б. Линейное программирование: Теория, методы и приложения. — М.: Наука, 1969.

КОМПЛЕКСНЫЕ ЗАДАЧИ

4.1. ⁴ Компания MANCO производит три вида продукции: PI, Р2 и РЗ. В произ­водственном процессе используются материалы Ml и М2, обрабатываемые на станках С1 и С2. В следующей таблице приведены данные, характеризующие производственный процесс.

⁴ Задача основана на материалах статьи D. Sheran, "Post-Optimal Analysis in Linear Pro­gramming — The Right Example", HE Transactions, Vol. 16, No. 1, March 1984, pp. 99-102.

Комплексные задачи

Единицы	К-во ресурсов на единицу изделия Ежедневный фонд
Ресурсы измерения	Р1	Р2	РЗ	ресурсов
Время работы станка С1 Минуты
Время работы станка С2 Минуты
Материал М1 Фунты
Материал М2 Фунты

Ежедневный объем производства изделия Р2 должен быть не менее 70 единиц, а изделия РЗ — не более 240 единиц. Доход на единицу изделия PI, Р2 и РЗ составляет соответственно 300, 200 и 500 долл.

Руководство компании разрабатывает стратегию для улучшения своего фи­нансового положения. Существуют такие предложения.

1. Увеличить на 20% доход от изделия РЗ, но при этом уменьшится объем его производства до 210 единиц.

2. Материал М2 является критическим фактором, ограничивающим текущее производство. Можно приобрести дополнительные объемы этого материала у сторонних поставщиков, но его цена за фунт будет на 3 долл. выше, чем у поставщиков, которые обслуживают компанию сегодня.

3. Увеличить фонд рабочего времени станков на 40 минут в рабочий день, одна­ко такое увеличение приведет к дополнительной стоимости эксплуатации каждого станка — 35 долл. в день.

4. Отдел маркетинга обосновал необходимость увеличения минимального объ­ема производства продукта Р2 с 70 до 100 единиц.

5. Время обработки единицы изделия Р1 на станке С2 можно уменьшить до 2 минут с дополнительной стоимостью 4 долл. в рабочий день.

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

4.2. Компания Reddy Mikks планирует в будущем расширить свое производство. Изучение ситуации на рынке красок показало, что компания может увеличить объем продаж на 25%. План развития производства можно разработать на ос­нове следующих предложений. (Обратитесь к примеру 3.3.1 за детальной ин­формацией о модели ЛП для этой компании и ее решении.)

Предложение 1. Поскольку рост продаж на 25% приведет к увеличению до­хода примерно на 5250 долл., стоимость дополнительных объемов сырья Ml и М2 составляет 750 и 500 долл. за тонну; следовательно, для обеспечения рос­та объема производства потребуется 5250/((750 + 500)/2) = 8,4 тонны сырья Ml и столько же сырья М2.

Предложение 2. Потребление сырья Ml и М2 должно возрасти на 6 и 1,5 тонны соответственно, так как эти величины соответствуют 25% текущего уровня потребления сырья (равного 24 тоннам для сырья Ml и 6 тоннам для сырья М2). Поскольку в текущем оптимальном решении оба этих ресурса дефицит­ны, увеличение их потребления на 25% должно привести к такому же увели­чению производства краски, т.е. конечного продукта.

Какие выводы вы можете сделать относительно этих предложений? Предло­жите несколько подходов к решению данной проблемы.

Глава 4. Двойственность и анализ чувствительности

4.3. Анализ чувствительности одновременно на допустимость и оптималь­ность решения задачи ЛП. Предположим, что в модель компании Reddy Mikks одновременно внесены следующие изменения. Доход от тонны крас­ки для наружных работ равен 1000 долл., а краски для внутренних ра­бот — 4000 долл. Ежедневное потребление сырья Ml и М2 ограничено 28 и 8 тоннами соответственно.

1. Покажите, что внесенные изменения приведут к потере текущим оптималь­ным решением как свойства оптимальности, так и допустимости.

2. Используя обобщенный симплексный алгоритм из раздела 4.4.2, найдите новое оптимальное допустимое решение.

ГЛАВА 5

ТРАНСПОРТНЫЕ МОДЕЛИ

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

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

5.1. ОПРЕДЕЛЕНИЕ ТРАНСПОРТНОЙ МОДЕЛИ

На рис. 5.1 показано общее представление транспортной задачи в виде сети с т пунктами отправления и п пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой (t, j), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: стоимость с, перевозки единицы груза из пункта i в пункт j и количество перевозимого груза х. Объем гру­зов в пункте отправления / равен а,, а объем грузов в пункте назначения j — b. За­дача состоит в определении неизвестных величин х, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, налагаемым на объемы грузов в пунктах отправления (предложения) и пунктах назначения (спрос).

194 Глава 5. Транспортные модели

Пункты отправления Пункты назначения

Объемы предложений

Рис. 5.1. Представление транспортной задачи

Пример 5.1.1

Автомобильная компания MG Auto имеет три завода в Лос-Анджелесе, Детройте и Новом Орлеане и два распределительных центра в Денвере и Майами. Объемы производства заводов компании в следующем квартале составят соответственно 1000, 1500 и 1200 автомобилей. Ежеквартальная потребность распределительных центров составляет 2300 и 1400 автомобилей. Расстояния (в милях) между завода­ми и распределительными центрами приведены в табл. 5.1.

Таблица 5.1

	Денвер	Майами
Лос-Анджелес
Детройт
Новый Орлеан

Транспортная компания оценивает свои услуги в 8 центов за перевозку одного ав­томобиля на расстояние в одну милю. В результате получаем следующую стоимость перевозок (с округлением до доллара) по каждому маршруту.

Таблица 5.2

	Денвер (1)	Майами (2)
Лос-Анджелес (1)
Детройт (2)
Новый Орлеан (3)

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