Оптимизационные задачи в экономике и алгоритмы решения некоторых задач линейного программирования

Учебное пособие по курсу

«МАТЕМАТИКА»

САНКТ-ПЕТЕРБУРГ 2004

Авторы: И.В.Вагурина, А.Е. Иванов, И.В.Медведева, Е.А.Смирнова, С.В.Ульянов

Рассмотрены проблемы математической формализации экономических оптимизационных задач, алгоритмы их геометрического и аналитического решения.

Учебное пособие предназначено для студентов заочной и заочной сокращенной форм обучения специальностей 06.08.00, «Экономика и управление на предприятии торговли и общественного питания», 06.05.00 «Бухгалтерский учет, анализ и аудит», 35.11.00 «Товароведение и экспертиза товаров», изучающих раздел «Математическое программирование» дисциплины «Математика».

Рецензент; доктор физ.-мат.наук, проф. А.Ю.Вальков (ИВЭСЭП)

§1. Математическая формализация оптимизационной проблемы

Искусство управления может рассматриваться как искусство выбора наилучшей с точки зрения управляющего альтернативы среди всех реализуемых альтернатив. В математике процесс выбора наилучшей альтернативы принято называть оптимизацией. Как известно, одним из основных отличий науки от искусства является возможность алгоритмизации. Воспользуемся простейшей задачей производственного планирования [Mathur, с. 159] и сформулируем алгоритм постановки оптимизационной задачи.

! 1Математическая формализация оптимизационной проблемы

Фирма Creative Coffees производит и продает два сорта кофе: Regular и Decaf. На текущий месяц запас кофейных зерен на складе фирмы составляет 200 тонн, а суммарное время жарки зерен ограничено 300 часами. Каждая тонна кофе Regular производится из одной тонны зерен, обжариваемых в течение одного часа, и приносит производителю прибыль в размере $3000. Каждая тонна кофе Decaf также производится из одной тонны зерен, но обжариваемых в течение двух часов, и приносит фирме прибыль в размере $5000. Представим условия задачи в табличной форме:

Таблица 1

	Regular (т)	Decaf (т)	Запас сырья
Зерна (т)
Время жарки (ч)
Прибыль от продажи ($1000/т)

Определим план выпуска кофе, при котором прибыль фирмы за текущий месяц будет максимальна.

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

Ø Укажем переменные, подлежащие определению в результате решения задачи, и введем понятие плана.

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

x ₁ – количество кофе Regular, которое следует произвести в текущем месяце,

x ₂ – количество кофе Decaf, которое следует произвести в текущем месяце,

и назовем вектор x =(x ₁, x ₂) планом выпуска.

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

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

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

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

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

Временные ограничения – это ограничения на время, отпущенное на решение пробле­мы.

Логические ограничения – это ограничения, связанные с природой оптимизируемых перемен­ных (например, неотрицательность цен, объемов затрат ресурсов и потребления товаров).

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

Ø Составим уравнения и неравенства, определяющие множество допустимых планов.

Допустимость плана в задачах производственного планирования определяется, прежде всего, тем, хватит ли имеющихся в наличии ресурсов на его реализацию. Выпуск x ₁ тонн кофе Regular требует x ₁ тонн кофейных зерен и x ₁ часов их жарки, а выпуск x ₂ тонн кофе Decaf требует x ₂ тонн кофейных зерен и 2 x ₂ часов их жарки. Таким образом, план x =(x ₁, x ₂) допустим, если

(1)

Производственные ограничения дополняются логическими ограничениями, связанными с природой введенных в рассмотрение переменных. В данном случае объемы выпуска товаров не могут быть отрицательными: x ³0. (2)

Рассмотрим геометрическую интерпретацию понятий: план, допустимый план, множество допустимых планов. Введем в рассмотрение декартову прямоугольную систему координат с осями, соответствующими оптимизируемым переменным, и, учитывая неравенство (2), изобразим ее первый квадрант (рис. 1). Любая точка в нем – план выпуска x =(x ₁, x ₂), причем план допустим, если его координаты удовлетворяют соотношениям (1), и не допустим – в противном случае.

Изобразим все планы, на которые хватит зерен кофе: x ₁+ x ₂£200. С этой целью построим отрезок прямой x ₁+ x ₂=200. На этом отрезке лежат планы выпуска, полностью исчерпывающие запас зерен, ниже – планы, на которые зерен хватит с избытком, выше – не допустимые планы.

Изобразим все планы, на реализацию которых хватит времени: x ₁+2 x ₂£300. С этой целью построим отрезок прямой x ₁+2 x ₂=300. На этом отрезке лежат планы выпуска, полностью исчерпывающие запас времени, ниже – планы, на которые времени хватит с избытком, выше – не допустимые планы.

Таким образом, множество допустимых планов – есть затененная область X на рис. 1 (множество планов, на реализацию которых хватит и первого, и второго ресурса):

Рис. 1 Допустимое множество в проблеме производственного планирования

6 Почему невозможно реализовать план y, план z (рис. 1)?

Возникает вопрос: какой из допустимых планов является лучшим для про­изводителя?

F 3. Функция, сопоставляющая альтернативам действительные числа, называется целевой (критериальной), если большее (меньшее) ее значение указывает на строго более предпочтительную альтернативу, а одинаковые значения – на равноценные альтернативы.

Ø Построим целевую (критериальную) функцию

В рассматриваемой задаче из двух допустимых планов лучшим является тот, который принесет фирме большую прибыль. При реализации плана x =(x ₁, x ₂) прибыль составит

p(x)=3 x ₁+5 x ₂

тысяч денежных единиц.

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

Предположим, имеется n оптимизируемых переменных, и, соответственно, план x является n –мерным вектором. Обозначим допустимое множество через X, целевую функцию через F.

F 4. Глобальным максимумом (минимумом) функции F (x) на множестве X называется та­кой допустимый вектор х *Î X, что

F (x *) ³ F (x) (F (x *) £ F (x)) " x Î X.

(3)

G Максимумы и минимумы функции принято называть ее экстремумами.

F 5. Задача нахождения глобального максимума (минимума) функции F (x) на множестве X называется задачей математического программирования (ЗМП) и записывается в виде

F (x) ® max, x Î X (F (x) ® min, x Î X).

(4)

Решение задачи (4) обозначается

x * = argmax F (x), x Î X, (x * = argmin F (x), x Î X),

и называется оптимальным планом. Число F (x *) называется значением задачи (4) и обозначается max F (x) (min F (x)).

F 6. Решить ЗМП – значит найти все ее решения или доказать, что их не существует.

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

p(x)=3 x 1+5 x 2 ® max,

(5)

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

Алгоритм математической формализации оптимизационной проблемы

Ø Указать переменные, подлежащие определению в результате решения задачи, ввести понятие плана

Ø Составить уравнения и неравенства, определяющие множество допустимых планов

Ø Построить целевую (критериальную) функцию

Ø Выписать получившуюся задачу математического программирования

F 7. Задача математического программирования, целевая функция которой является линейной, а допустимое множество задано системой линейных уравнений и неравенств, называется задачей линейного программирования (ЗЛП).

F 8. ЗЛП называется стандартной задачей линейного программирования, если

все ограничения выражены линейными неравенствами одинакового направления (как правило, £),

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

Таким образом, задача (5) – стандартная задача линейного программирования. Если ввести обозначения

ее можно записать в виде

p(x)= сx ® max, Ax £ b, x ³0.

F 9. ЗЛП называется канонической задачей линейного программирования, если

все ограничения выражены линейными равенствами,

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

Для приведения стандартной задачи линейного программирования к канонической следует

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

@ 1. Перейдите от стандартной ЗЛП (5) к канонической.

@ 2. Каждый галлон молока, фунт сыра и яблок обеспечивает организм определенным коли­чеством миллиграмм про­теина и витаминов A, B, C в соответствии с данными приведенной ниже таблицы. Наряду с этими данными, таблица содержит ин­формацию о минимальных ежедневных потребностях организма в вышеупомянутых веществах, пред­ставленную Де­партаментом сельского хозяйства США. Кроме того, в таблицу включены данные о минимальном количестве каждого из продуктов, которое должно войти в меню, и цены продуктов.

Таблица 1

	Молоко (мг/галлон)	Сыр (мг/фунт)	Яблоки (мг/фунт)	Минимальные потребности организма (мг)
Протеины
Витамин A
Витамин B
Витамин С
Минимальное количество в диете	0,5 гал.	0,5 фунта	0,5 фунта
Цена ($)	2,15	2,25	1,25

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

§2. Геометрическая интерпретация стандартной задачи линейного программирования

Специфические особенности ЗЛП (линейная целевая функция, линейные ограничения) позволяют получить ряд геометрических интерпретаций, связанных с поиском ее решения.

! 1Задача планирования товарооборота

При продаже товаров А и В используется три вида ресурсов: R ₁, R ₂, R ₃(например, R ₁– рабочее время; R ₂– полезная площадь торгового зала; R ₃– упаковочный материал). Сведения о количестве ресурсов, необходимых для продажи единицы каждого товара, обеспеченности торгового предприятия этими ресурсами и ценах, по которым товары продаются, приведены в следующей таблице:

Таблица 1

Ресурсы	Товары	Запас ресурсов
A	B
R 1
R 2
R 3
Цена товара

Составим план продажи товаров, обеспечи­вающий максимальный товарооборот.

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

Ø Укажем переменные, подлежащие определению в результате решения задачи, и введем понятие плана.

Обозначим через X ₁ и X ₂ запланированный объем продажи товаров А и В и назовем вектор X =(X ₁, X ₂) планом продажи товаров.

Ø Составим уравнения и неравенства, определяющие множество допустимых планов.

Из экономического смысла величин X ₁ и X ₂ следует, что X ₁³0, X ₂³0.

Из таблицы 1 следует, что продажа X ₁ единиц товара А требует 2 X ₁ единиц первого ресурса и 2 X ₁ единиц второго ресурса, а продажа X ₂ единиц товара В требует 3 X ₂ единиц первого ресурса, X ₂ единиц второго ресурса и 3 X ₂ единиц третьего ресурса. Таким образом, план продажи X =(X ₁, X ₂) допустим, если для его реализации достаточно имеющихся в наличии ресурсов:

(1)

Ø Построим целевую (критериальную) функцию

Из последней строчки таблицы 1 следует, что при реализации плана X =(X ₁, X ₂) товарооборот составит E (x)=7 X ₁+5 X ₂ денежных единиц.

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

(2)

Изобразим на плоскости допустимое множество задачи (2). Учитывая неотрицательность оптимизируемых переменных, ограничимся первой четвертью декартовой прямоугольной системы координат O X ₁ X ₂.

Рис. 1 Построение допустимого множества задачи планирования товарооборота

Последовательно изобразим планы, полностью исчерпывающие запас первого (отрезок I), второго (отрезок II) и третьего ресурса (отрезок III), а затем стрелками укажем те полуплоскости, в которых лежат планы, на которые соответствующего ресурса хватит с избытком. Допустимым множеством задачи (2) является пересечение вышеупомянутых полуплоскостей (множество планов, на реализацию которых хватит всех ресурсов) (рис. 1).

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

E (x)=7 X 1+5 X 2= d,

(3)

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

Изобразим некоторую поверхность уровня, соответствующую, например, d =14, которая представляет собой прямую, заданную уравнением:

7 X ₁+5 X ₂=14.

Рис. 2 Геометрическое решение СЗЛП

Стрелка на рис. 2 указывает направление, в котором лежат планы продаж с большим (чем 14) товарооборотом, в противоположном направлении лежат планы с меньшим товарооборотом.

Поскольку в направлении стрелки лежат допустимые планы задачи (2), можно добиться большего товарооборота, перемещая поверхность уровня параллельно самой себе до тех пор, пока она пересекает допустимое множество. План A (рис. 2) является планом с наибольшим товарооборотом, поскольку все отличные от A планы лежат ниже поверхности уровня, которому принадлежит план A.

Координаты точки А удовлетворяют уравнениям прямых, на пересе­чении которых она лежит. Решая систему

получаем оптимальное решение задачи: X *=(5, 3) (X ₁=5; X ₂=3). При этом товарооборот составит

Е_max =7´5 + 5´З = 50

денежных единиц.

§3. Симплекс-метод

В настоящем параграфе рассмотрим алгоритм основного аналитического метода решения задач линейного программирования – симплекс-метода.

1. Симплекс-метод применяется только к канонической ЗЛП (F 1.9).

Приведем задачу планирования товаро­оборота к канонической форме. Введем дополнительные переменные:

(1)

Переменные Y ₁, Y ₂ и Y ₃ имеют очевидный экономический смысл – это остатки сырья R ₁, R ₂, R ₃при реализации плана X =(X ₁, X ₂).

2. Алгоритм симплекс-метода, рассматриваемый в настоящих методических указаниях, применяется только к задаче минимизации.

Задачу нахождения максимума всегда можно свести к задаче нахождения минимума, сменив знак у целевой функции, причем:

обе задачи будут иметь одно и то же множество решений,

значения задач будут различаться знаком.

Таким образом, задачу об отыскании максимума функции Е можно свести к задаче отыска­ния минимума функции Е ' = – Е. Для единообразия схемы приме­нения симплекс-метода мы будем говорить о нахождении только ми­нимума функции. Поэтому задачу планирования товарооборота будем рассматривать как задачу минимизации функции

Е ' = –7 X 1–5 X 2

(2)

на множестве всех допустимых планов.

Итак, при решении симплекс-методом задачи планирования то­варо­обо­рота используется следующая ее формулировка:

найти такие неотрицательные значения переменных X ₁, X ₂, Y ₁, Y ₂, Y ₃ (план Z =(X ₁, X ₂, Y ₁, Y ₂, Y ₃)), удовлетво­ряющие системе (1), при которых функция (2) достигает минимума.

В системе уравнений (1) переменные Y ₁, Y ₂, Y ₃ выражены че­рез X ₁, X ₂. В соответствии с этим переменные Y ₁, Y ₂, Y ₃ называют­ся базисными, а переменные X ₁, X ₂ – свободными.

3. Из геометрической интерпретации задачи следует, что опти­мальное решение достигается в одной из вершин многоугольника области допустимых решений (ОДР). Вершины ОДР называются опорными точками, а соответ­ствующие допустимые решения — опорными решениями задачи (опорными планами).

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

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

Рассмотрим алгебраические основы симплекс-метода на примере задачи планирования товарооборота.

Решение задачи симплекс-методом начинается с нахождения первого опорного плана. Положив в (1) свободные переменные X ₁ и X ₂ равными нулю, получаем:

X ₁= X ₂=0, Y ₁=19, Y ₂=13, Y ₃=15.

При этом Е ' = Е = 0. Так как значения всех переменных неотри­ца­тельны, полученный план Z ¹=(0, 0, 19, 13, 15) является опорным. Согласно этому плану товары не продаются и товарооборот равен нулю. Естественно, такой план не может быть оптимальным.

Этот вывод следует и из формальных рассуждений: увеличивая любую из переменных X ₁ и X ₂ (что, очевидно, возможно), мы уменьшаем значение функции Е ' = –7 X ₁–5 X ₂, так как эти перемен­ные входят в выражение Е ' с отрицательными коэффициентами.

Будем увеличивать X ₁, оставляя X ₂ = 0. Новый опорный план будет достигнут, как только одна из переменных Y ₁, Y ₂ или Y ₃ обратится в нуль. Из (1) имеем: Y ₁ = 0 при X ₁ = 19/2, Y ₂ = 0 при X ₁ = 13/2; Y ₃ =15 при любом значении X ₁. Таким образом, в новом опорном решении

X ₁ = min {19/2, 13/2}=13/2,

при этом X ₂ = Y ₂ = 0.

Чтобы проверить, является ли новый опорный план оптимальным, нужно из уравнений (1) выразить пере­менные X ₁, Y ₁ и Y ₃ через X ₂ и Y ₂, а затем подставить полученное выражение X ₁ в функцию Е '. Таким образом, мы заменим в системе (1) свободную переменную X ₁ на бывшую базисную Y ₂.

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

Запишем в стандартной форме нашу задачу:

(3)

По стандартной форме записи системы и целевой функции составляется симплексная таблица, в которую записы­ваются свободные члены и коэффициенты при свободных переменных:

Таблица 1

Базисные переменные	Свободный член	Свободные переменные
X 1	X 2
Y 1				19/2
Y 2				13/2
Y 3				–
Е '

Эта таблица соответствует первому опорному плану: свободные переменные X ₁и X ₂ равны нулю, а базисные перемен­ные Y ₁, Y ₂, Y ₃ и функция Е' равны соответствующим свободным членам.

План оптимален, если в столбцах свободных переменных в последней строке таблицы нет поло­житель­ных коэффициентов.

Таким образом, рассматриваемый план не оптимален. Чтобы уменьшить функцию Е', следует увеличить свободную переменную, которой соответствует положительный коэффициент в строке Е' (например, X ₁). В новом опорном плане обратится в нуль та базисная переменная, для которой отношение свободного члена к соответствующему (положительному!) коэффициенту столбца X ₁ будет минимальным (эти отношения записываются в последнем столбце таблицы). В нашем примере это переменная Y ₂.

Для вычисления нового опорного плана следует в системе уравне­ний (1) заменить свободную переменную X ₁ на базисную Y ₂.

Соответствующая симплексная таблица (симплекс-таблица) будет иметь следующий вид:

Таблица 2

Базисные переменные	Свободный член	Свободные переменные
Y 2	X 2
Y 1
X 1
Y 3
Е '

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

Алгоритм преобразования симплекс-таблицы

1. В исходной таблице (таблица 3) выделяются столбец и строка, соответствующие тем переменным, которые меняются местами. Они называются разрешающим столбцом и разрешающей строкой (в на­шем примере это столбец X ₁и строка Y ₂). Элемент, стоящий на их пересечении, называется разрешающим элементом.

Таблица 3

Базисные переменные	Свободный член	Свободные переменные
X 1	X 2
Y 1
–13	–1	–1
Y 2		13/2				1/2
	1/2
Y 3
Е '
–91/2	–7/2	–7/2

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

3. Каждый элемент разрешающей строки (кроме разрешающе­го элемента) умножается на l, результат записывается в правом нижнем углу той же клетки.

4. Каждый элемент разрешающего столбца (кроме разрешающе­го элемента) умножается на (–l), и результат записывается в пра­вом нижнем углу той же клетки.

5. В разрешающей строке выделяются все старые элементы (кроме разрешающего). В разрешающем столбце выделяются все новые элементы, за исключением клетки с разрешающим элементом.

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

7. Таблицу переписывают, при этом заменяют:

выделенную свободную переменную – на выделенную базисную;

элементы разрешающего столбца и разрешающей строки – на числа, стоящие в правых нижних углах клеток;

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

Выполнив преобразование таблицы 3 в соответствии с приведенным алгоритмом, получим следующую таблицу:

Таблица 4

Базисные переменные	Свободный член	Свободные переменные
Y 2	X 2
Y 1		–1
X 1	13/2	1/2	1/2
Y 3
Е '	–91/2	–7/2	3/2

Этой таблице соответствует следующая запись системы уравнений и функции Е ':

В новом опорном плане Z ²=(13/2, 0, 6, 0, 15)

Y ₂= X ₂=0, Y ₁=6, X ₁=13/2, Y ₃=15, Е '= –91/2, Е = – Е '= 91/2.

Согласно этому плану, следует продавать 13/2 единиц товара А и не продавать товар В; при этом остатки ресурсов R ₁и R ₃ равны, соответственно, 6 и 15 единицам, а ресурс R ₂ расходуется полностью. Товарооборот равен 91/2.

Этот план не оптимален, так как в последней строке таблицы есть положительный коэффициент при свободной переменной X ₂, а зна­чит, увеличивая X ₂, можно уменьшить Е' (увеличить товарооборот). Выделим в таблице 5 разрешающий столбец X ₂. Мини­мальное из отношений свободных членов к положительным коэффи­циентам столбца X ₂ определяет в качестве разрешающей строки строку Y ₁.

Таблица 5

Базисные переменные	Свободный член	Свободные переменные
Y 2	X 2
Y 1			–1
			–1/2	1/2
X 1	13/2	–3/2	1/2		1/2
	1/4		–1/4
Y 3
–9	3/2	–3/2
Е '	–91/2		–7/2		3/2
–9/2	3/4	–3/4

Применив алгоритм преобразования симплекс-таблицы, получим следующую таблицу:

Таблица 6

Базисные переменные	Свободный член	Свободные переменные
Y 2	Y 1
X 2		–1/2	1/2
X 1		3/4	–1/4
Y 3		3/2	–3/2
Е '	–50	–11/4	–3/4

Симплекс-таблице 6 соответствует опорный план Z ³=(5, 3, 0, 0, 6)

Y ₂ = Y ₁ = 0, X ₂ = 3, X ₁ = 5, Y ₃ = 6,

и значение оптимизируемой функции Е ' = – 50 (соответственно, Е = 50).

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

Таким образом, в рассматриваемой задаче оптимальным является следующий план: продавать 5 единиц товара А и 3 единицы товара В. При этом полностью расходуются ресурсы R ₁ и R ₂и остаются неиспользован­ными 6 единиц ресурса R ₃. Такой план обеспечивает максимальный товарооборот, равный 50 рублям.

§4. Постановка транспортной задачи

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

Имеется т пунктов хранения (баз) A ₁, A ₂,..., A_m, на которых сосредоточены запасы некоторого товара в количествах соответствен­но a ₁, a ₂,..., a_m условных единиц. Кроме того, имеется п пунктов потребления (магазинов) B ₁, B ₂,..., B_n, подавших заявки соответствен­но на b ₁, b ₂,..., b_n единиц товара. Стоимость перевозки единицы това­ра из пункта A_i (i = 1, 2, …, m) в пункт B_k (k = 1, 2, …, n) составляет c_ik денежных единиц). Предполагается, что общая стоимость пере­возки партии товара пропорциональна количеству товара в этой партии.

Условия транспортной задачи могут быть представлены с помощью матрицы транспортной задачи:

Если суммарное предложение товара равно суммарному спросу на него

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

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

вывезти весь хранящийся на базах запас товара,

удовлетворить заявки всех магазинов,

добиться минимальной суммарной стоимости всех перевозок.

Построим математическую модель транспортной задачи.

Ø Укажем переменные, подлежащие определению в результате решения задачи, и введем понятие плана

Обозначим через x_ik количество товара, направляемого из пункта A_i в пункт B_k (i = 1, 2, …, m; k = 1, 2, …, n). Таким образом, в задаче имеется m ´ n оптимизируемых переменных, и план в транспортной задаче имеет вид x =(x ₁₁, x ₁₂, …, x_mn).

G План перевозок в транспортной задаче удобно представить в виде матрицы

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

Ø Составим уравнения и неравенства, определяющие множество допустимых планов

План x =(x ₁₁, x ₁₂, …, x_mn) является допустимым, если

он обеспечивает вывоз всего хранящегося на базах товара:

он удовлетворяет заявки всех магазинов:

все оптимизируемые переменные неотрицательны: x ³0.

Ø Построим целевую (критериальную) функцию

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

E (x) = c ₁₁ x ₁₁ + c ₁₂ x ₁₂ + … + c_mn x_mn .

Ø Выпишем получившуюся задачу математического программирования

Поскольку транспортная задача является задачей линейного программирования, она может быть решена симплекс-методом. В си­лу специфики задачи можно вместо симплекс-таблиц пользовать­ся таблицами более простого вида (так называемыми транспортными таблицами):

Таблица 1

Базы	Магазины	Запас
B 1	B 2	…	Bn
A 1		c 11		c 12	…		c 1 n	a 1
x 11		x 12		x 1 n
A 2		c 21		c 22	…		c 2 n	a 2
x 21		x 22		x 2 n
…	…	…	…	…	...
Am		cm 1		cm 2	…		cmn	am
xm 1		xm 2		xmn
Спрос	b 1	b 2	...	bn

Решение транспортной задачи может быть получено путем не­которых преобразований транспортной таблицы. Как и в общем случае, оптимальное решение ищется среди опорных решений. В системе ограничений-равенств транспортной задачи можно выделить т + п – 1 базисных переменных, выразив их через остальные (сво­бодные). В опорном решении свободные переменные равны нулю. Эти нули в таблицу не записываются, а соответствующие (пустые) клетки таблицы называются свободными клетками. Заполненные клетки таблицы соответствуют базисным переменным и называются базисными клетками. Таким образом, в транспортной таблице, представляющей опор­ный план, имеется т + п – 1 заполненных клеток.

§5. Алгоритм решения транспортной задачи

I. Определение опорного транспортного плана

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

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

! 1Построение опорного плана перевозок

Условия транспортной задачи заданы транспортной таблицей 1:

Таблица 1

Базы	Магазины	Запас
B 1	B 2	B 3	A 4
A 1
A 2
A 3
A 4
Спрос

Составим опорный план перево­зок методом наименьшей стоимости.

Заполним таблицу 1, начиная с клетки (A ₂, B ₂), в которой мы имеем минимальную стоимость перевозки (c ₂₂ = 1). За счет запаса базы A ₂ можно удовлетворить всю заявку магазина B ₂, поэтому записы­ваем 17 в клетку (A ₂, B ₂).

Следующую по величине стоимость, равную 2, имеем в клетке (A ₁, B ₄). Поскольку запас базы A ₁ меньше заявки магазина B ₄, в эту клетку записываем перевозку, равную запасу базы A ₁ (15 еди­ниц). Следующую по величине стоимость равную 3, имеем в клетках (A ₁, B ₂) и (A ₃, B ₄). Клетку (A ₁, B ₂) нельзя заполнять, поскольку запас ба­зы A ₁ уже исчерпан. Заполняем клетку (A ₃, B ₄), удовлетворяя оставшуюся часть заявки магазина B ₄ (5 единиц) за счет базы A ₃.

Рассуждая аналогично, заполняем остальные клетки в такой последовательности: (A ₂, B ₃), (A ₃, B ₃), (A ₃, B ₁), (A ₄, B ₁). Будем иметь:

Таблица 2

Базы	Магазины	Запас
B 1	B 2	B 3	A 4
A 1
A 2
A 3
A 4
Спрос

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

x =(0, 0, 0, 15, 0, 17, 14, 0, 6, 0, 14, 5, 22, 0, 0, 0),

или, в матричной форме,

Вычислим стоимость плана x:

E (x)=2´15+1´17+4´14+6´6+5´14+3´5+10´22=444.

Отметим, что число заполненных (базисных) клеток равно т + п – 1= 7, то есть, действительно построен опорный план перевозок.

G При построении опорного плана перевозок в рассмот­ренной задаче на каждом шаге, кроме последнего, либо исчерпы­вался запас базы (но оставалась невыполненной заявка), либо выполнялась заявка магазина (но оставалась неиспользованной часть запаса базы). Может оказаться, что на некотором (не послед­нем!) шаге будет одновременно выполнена заявка магазина и исчерпан запас базы, тогда число заполненных клеток окажет­ся меньше, чем т + п – 1. В этом случае следует записать нуле­вую перевозку в ту клетку, которая заполнялась бы, если бы оста­ток запаса данной базы не был бы равен нулю. Эта клетка в даль­нейшем считается базисной.

II. Проверка оптимальности транспортного плана методом потенциалов

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

Рассмотрим опорный план, построенный в таблице 2. Предположим, что мы хотим сделать свободную клетку (A ₄, B ₂) базисной клеткой или запланировать перевозку с четвертой базы во второй магазин. С этой целью запишем в клетку положительное значение, равное а еди­ниц:

Таблица 3

Базы	Магазины	Запас
B 1	B 2	B 3	A 4
A 1
A 2
		17– a		14+ a
A 3
6+ a				14– a
A 4
22– a		+ a
Спрос

Тогда, чтобы сумма объемов перевозок в каждой строке остава­лась равной ее запасу, а в столбце – заявке, нужно

уменьшить на а единиц объем перевозки в клетке (A ₄, B ₁),

увеличить на а единиц объем перевозки в клетке (A ₃, B ₁),

уменьшить на а единиц объем перевозки в клетке (A ₃, B ₃),

увеличить на а единиц объем перевозки в клетке (A ₂, B ₃),

уменьшить на а единиц объем перевозки в клетке (A ₂, B ₂).

Таким образом, осуществляется «переброска» а единиц товара по замкнутому контуру, изображенному пунктиром в таблице 3. Такой контур называется циклом.

Цикл — это замкнутая ломаная, соединяющая несколько клеток таблицы и совершающая в каждой из них поворот на 90°. Две последовательные вершины цикла лежат либо в одной строке, либо в одном столбце. В одной из них объем перевозки увеличивается (в клетке ставится знак +), в другой — уменьшается на столько же единиц (в клетке ставится знак –). Примеры циклов различ­ных конфигураций показаны на рис. 1:

–	+				–	+				–	+
					+
		–	+					–
+			–				–	+		+	–

Рис. 1 Примеры циклов

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

Можно доказать, что для любой свободной клетки в опорном плане перевозок существует единственный цикл пересчета. Для того, чтобы одна из базисных клеток после переброски стала свободной, значение перевозки в этой клетке должно стать равным нулю. Ясно, что это может быть только клетка, в которой стоит знак (–). Поэтому количество товара, перебрасываемого по циклу пересчета, должно быть равно наименьшей из величин перевозок, стоящих в отрицатель­ных вершинах цикла. Например, если в таблице 3 положить а=min (22, 14, 17)=14, то, перебросив 14 единиц товара по ука­занному циклу пересчета, приходим к новому опорному плану:

Таблица 4

Базы	Магазины	Запас
B 1	B 2	B 3	A 4
A 1
A 2