Posobie1

объема и считают транспортные расходы ci, n +1 равными 0 для всех i. Таким образом, при введении виртуального получателя транспортная задача

	m	n 1	m	n
становится сбалансированной: ai = bj			, где bn+1 = ai –	b j . Мате-
	i 1	j 1	i 1	j 1
матическая модель такой экономической ситуации имеет вид:
	m	n 1
	L(X ) = cij xij		min
	i 1	j 1
при ограничениях:
	n 1
	xij = ai для i =1, 2,…, m;
	j 1
	m
	xij = bj для j =1, 2,…, n, n + 1.
	i 1
xij 0 для i =1, 2,…, m и j =1, 2,…, n, n + 1.
m	n
Если же ai b j , то вводят гипотетический (виртуальный) пункт
i 1	j 1
		n	m
отправления Аm+1,	содержащий am+1 b j		ai единиц готового к от-
		j 1	i 1

правке груза, и транспортные расходы cm+1,j считают равными 0 для всех j. Такое изменение начальных условий также приводит к тому, что транс-

m 1	n
портная задача становится сбалансированной: ai	= bj . Математиче-
i 1	j 1

скую модель описанной ситуации предлагается составить самостоятельно. Замечание 4. ЛПР могут руководствоваться, вырабатывая свою стра-

тегию, принципом максимизации суммарного дохода от перевозок. Тогда транспортная ЗЛП задается следующими элементами:

двумя конечными множествами {А1,…, Аm} и {В1,…, Вn}, экономическая интерпретация элементов которых совпадает с интерпретацией соответствующих элементов в рассмотренной выше минимизационной транспортной задаче;

неотрицательными векторами (a1,…, am) и (b1,…, bn), координаты которых ai и bj определяют количество единиц груза, готового к отправлению и получению в пунктах Ai и Bj соответственно;

матрицей C = (cij), где cij — доход от перевозки единицы груза из пункта Ai в пункт Bj.

В этом случае оптимальный	план	X опт должен максимизировать
суммарный доход от перевозок:
m	n
L(X ) = cij xij		max.
i 1	j 1

11

2. Некоторые особенности транспортной задачи

Приведенная выше формулировка транспортной задачи не единственная с точки зрения применения транспортной задачи для решения экономических задач. Поясним это на двух примерах.

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

L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 min (max)

при ограничениях:

x11 + x12 + x13 = 110, x21 + x22 + x23 = 100, x11 + x21 = 60,

x12 + x22 = 80, x13 + x23 = 70,

x11 0, x12 0, x13 0, x21 0, x22 0, x23 0.

Решение. 1) Сначала рассмотрим случай, когда в качестве критерия экономической эффективности выступает минимум указанной величины:

L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 min.

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

Вариант 1 примера 1. Фирма имеет два склада и трех оптовых покупателей. Конкретные данные о загруженности каждого из складов (в тоннах), потребности каждого покупателя (в тоннах) и стоимости перевозки (усл. ед. за 1 т) приведены в таблице 1.

					Таблица 1
		Стоимость перевозок к покупателям			Наличие
		B1	B2	B3	груза
Склады	A1	4	8	9	110
	A2	7	3	5	100
Потребности		60	80	70

Составить оптимальный план перевозок, имеющий минимальные транспортные расходы.

Неформальные пояснения к решению варианта 1. Экономической ин-

терпретацией переменной xij является количество товара, поставляемого

со склада Ai покупателю Bj, а величина L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + + 5x23 трактуется как общая стоимость всех перевозок. Общий объем за-

пасов на складах совпадает с общим объемом запросов покупателей:

2	3
ai = 110 + 100 = 210 (т),	bj = 60 + 80 + 70 = 210 (т).
i 1	j 1

12

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

		x11		B1	b1		= 60
a1 = 110	A1	x12
	x21		x13		B2		b2 = 80
		x22
a2 = 100	A2
			x23		b3	= 70
				B3

Рис. 1. Схематическое изображение транспортной задачи

Решение задачи, соответствующее для варианта 1 оптимальному пла-

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

2) Теперь рассмотрим случай, когда в качестве критерия экономической эффективности выступает максимум указанной величины:

L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 max.

Вариант 2 примера 1. Мастерская имеет два станка, каждый из которых может выполнять три операции по обработке деталей (порядок выполнения операций не важен). Продолжительность выполнения первой операции составляет 60 часов, второй — 80, третьей — 70. Время работы первого и второго станков равно соответственно 110 и 100 часам. Производительность за час (в количестве деталей) первого станка при выполнении первой операции равна 4, при выполнении второй — 8, третьей — 9. Аналогичная производительность второго станка равна соответственно 7, 3 и 5. Составить план временнóй загрузки станков по выполнению каждой операции, при котором можно было бы обработать наибольшее количество деталей.

Сформулированная задача носит название задачи об использовании производственного оборудования (мощностей).

13

Неформальные пояснения к решению варианта 2. Обозначив через A1

и A2 первый и второй станки, а через B1, B2 и B3 первую, вторую и третью операции соответственно, условия данной задачи удобно записать в виде таблицы 2 (сравните с соответствующей таблицей варианта 1).

Таблица 2

			Производительность станков			Время работы
			при выполнении операций
						станков
			B1	B2	B3
	Станки	A1	4	8	9	110
		A2	7	3	5	100
	Продолжительность		60	80	70
	выполнения операции

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

Обозначим через xij количество часов, которое требуется при выполне-

нии на i-м станке j-й операции. При этом, конечно, xij 0 (i = 1, 2, j = 1, 2, 3). Тогда xi1 + xi2 + xi3 — общее количество часов, которое требуется при

выполнении на i-том станке каждой из трех операций, а x1j +x2j — суммарная продолжительность выполнения j-й операции на каждом из двух станков. Это приводит к системе линейных равенств

x11 + x12 + x13 = 110, x21 + x22 + x23 = 100, x11 + x21 = 60,

x12 + x22 = 80, x13 + x23 = 70.

Заметим, что суммарная продолжительность выполнения операций совпадает с суммарным временем работы станков: 60 + 80 + 70 = 110 + + 100 (ч). Обозначим через cij производительность i-го станка при выполнении j-й операции. Тогда количество деталей, обработанных на i-м станке при выполнении j-й операции, будет равно cijxij. Общее же количество деталей, обработанных на двух станках при выполнении трех указанных

2	3
операций, составит cij xij = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23. В усло-
i 1	j 1

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

14

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

Анализ экономической ситуации варианта 2 подтверждает, что алго-

ритм решения транспортной задачи может быть использован при решении задач, далеких от транспортировки груза. Доказательством этого может служить и рассматриваемый ниже пример 2. Конечно, при решении таких задач необходимо учитывать их специфику, что должно отражаться в различных экономических интерпретациях переменных и констант, входящих в математические модели указанных задач. Так, например, если в «чисто» транспортной задаче коэффициенты целевой функции интерпретируются как транспортные расходы, а переменные — как количество перевозимого груза, то в задаче об использовании производственного оборудования коэффициенты целевой функции интерпретируются как производительность, а переменные — как затраты времени.

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

n	n
L(X) = cij xij		min(max)
i 1	j 1

при ограничениях:

n

xij j 1

=1 для i =1, 2,…, n; xij = 1 для j =1, 2,…, n.

i 1n

xij{0, 1} для i =1, 2,…, n и j =1, 2,…, n.

Решение. 1) Сначала рассмотрим случай, когда в качестве критерия экономической эффективности выступает минимум указанной величины.

Вариант 1 примера 2. Автомобильный завод планирует построить станции A1,…, An для технического обслуживания производимых им машин. Для строительства он выбрал города B1,…, Bn. Вырабатывая стратегию строительства, ЛПР решили руководствоваться принципом минимизации суммарных затрат на строительство указанных станций. Затраты на строительство станции Ai в городе Bj составляют cij. Необходимо определить оптимальную стратегию ЛПР.

Неформальные пояснения к решению варианта 1. Обозначим

xij = 1, если i - я станция строится в j - м городе,				j		) .
	(i 1; n,				1; n
0 в противном случае

Конечно, при такой интерпретации переменных

15

	n
	xij	= 1 для i =1, 2,…, n;
	j 1
	n
	xij	= 1 для j =1, 2,…, n,
	i 1
n	n
а cij xij — суммарные затраты на строительство станций, в миними-
i 1	j 1

зации которых заинтересованы ЛПР.

2) Рассмотрим случай, когда в качестве критерия экономической эффективности выступает максимум указанной величины:

Вариант 2 примера 2. В целях повышения привлекательности франшизы1 франчайзер2 решил организовать торговую точку. Для этого ему потребовалось ввести n новых штатных единиц для выполнения n видов работ. В результате объявленного конкурса было принято n сотрудников. Производительность i-го сотрудника при выполнении j-го вида работ равна cij. Необходимо распределить людей по видам работ таким образом, чтобы их суммарная производительность была бы максимальной.

Неформальные пояснения к решению варианта 2. Обозначим

	1, если сотрудник i назначаетс я на вид работ j,
			(i 1; n, j 1; n).
	xij=
	0	в противном случае
	n	n

Тогда cij xij — суммарная производительность сотрудников, в мак-

i 1 j 1

симизации которой заинтересован франчайзер.

1 Франшиза — контрольная лицензия, выданная одним лицом (франчайзером) другому (франчайзи), которая:

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

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

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

требует от франчайзи регулярно в течение всего периода франшизы выплачивать франчайзеру определенные денежные суммы в оплату франшизы или товаров, услуг, предоставляемых франчайзером франчайзи;

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

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

иформы продаж товаров или оказание услуг [Рудашевский В. Д., Фурщик М. А. Оптимальная стратегия развития франчайзинговой системы // Экономика и мат. методы. 1998. Т. 34. Вып. 2].

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

16

При этом

n

xij = 1 для i =1, 2,…, n;

j 1

n

xij = 1 для j =1, 2,…, n.

i 1

Задачи, математические модели которых описаны в примере 2, являются частными случаями транспортной задачи и носят название задач о сопоставлении (или назначениях).

3. Формулировка общей задачи линейного программирования

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

Требуется найти значения действительных переменных x1, x2,…, xn, при которых целевая функция (показатель эффективности)

L(X ) = c1x1 + c2x2 + ... + cjxj + ... + cnxn + c

принимает экстремальное значение при ограничениях:

a11x1 a12 x2 ...

a1 j x j ...

a1n xn b1,

a

x a

x

...

a

x

...

a

x

b ,

21 1

22

2

2 j

j

2n

n

2

............................................................

a x a

x

2

...

a x

j

...

a x

n

b ,

i1 1

i 2

ij

in

i

............................................................

amj x j

amn xn bm ,

am1x1 am2 x2

...

xk 0,

где aij, bi, cj, c — заданные постоянные величины, i = 1, 2,…, m, j = 1,

2,…, n, k 1, 2,..., n .

Заметим, что знак « » в ограничительных условиях выбран условно (для определенности), так как, например, неравенство ai1x1+...+ ainxn bi всегда можно заменить на эквивалентное ему неравенство – (ai1x1+...+ainxn) – bi,

а уравнение ai1x1+...+ainxn = bi — на систему неравенств ai1x1+...+ainxn bi и ai1x1+...+ ainxn bi. Стоит, однако, отметить, что на практике сведение

уравнений к неравенствам, как правило, осуществляют другим способом (см., например, решение транспортной задачи). Если все ограничительные условия, накладываемые на элементы решения, кроме требования xj 0, являются уравнениями, то в этом случае задачу линейного про-

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

вания (сокращенно КЗЛП). Ее примером может служить опять же транспортная задача. Заметим, что любая задача линейного программирования может быть приведена к канонической.

17

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

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

программирования и обозначают Х опт.

Формулировку общей задачи линейного программирования (сокращенно ОЗЛП) можно записать более компактно:

n

L(X) = с j x j + c max (min)

j 1

при ограничениях:

n

aij x j b i, i = 1, 2,…, m, xk 0, k 1, 2,..., n .

j 1

4.Геометрическая интерпретация ЗЛП

Рассмотрим задачу линейного программирования по нахождению максимума (минимума) целевой функции L(X) = c1x1 +...+ cnxn + c на до-

пустимом множестве Х , заданном с помощью системы линейных ограничений (нестрогих неравенств или уравнений).

Напомним некоторые определения.

Выпуклой линейной комбинацией элементов X1,…, Xk из пространства

Rn называют элемент X этого же пространства вида

X =1X1+…+ kXk, где все i 0 и 1+…+ k = 1.

Множество M Rn называется выпуклым, если M = или вместе с любыми двумя элементами X1 и X2 содержит и их произвольную выпуклую линейную комбинацию. Геометрически выпуклость множества M Rn означает, что вместе с любыми двумя своими точками оно содержит и весь отрезок, их соединяющий (рис.2).

X1 X2

X2

X1

Рис. 2. Различие между выпуклыми и невыпуклыми множествами из R2

18

Замечание 5. Такая геометрическая интерпретация выпуклости объясняется тем, что любая точка отрезка является выпуклой линейной комбинацией его концов. Действительно, если точки X, X1, X2 определяются в Rn соответственно координатами (x1,…, xn), (x11,…, x1n), (x21,…, x2n) и X —

произвольная точка отрезка X1X2, то x1 = x11+(1 )x21,…, xn = x1n + + (1 )x2n, 0 1. В сокращенном виде это запишется так:

X = X1+ (1 )X2, 0 1.

Примерами выпуклых множеств в R3 служат куб, шар, точка. Примером выпуклого множества в Rn может служить плоскость. Еще два примера выпуклых множеств в Rn описывает

Теорема 1. а) Множество решений системы ограничений задачи линейного программирования является выпуклым множеством;

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

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

найти максимум (минимум) линейной функции на выпуклом множестве.

Ограниченное множество решений системы ограничений ЗЛП назы-

вают выпуклым многогранником, а неограниченное — выпуклой много-

гранной областью. В R2 — это выпуклые многоугольники или выпуклые многоугольные области (см., например, рис. 3).

а)

б)

в)

г) д)

Рис. 3. Выпуклые многоугольники и выпуклые многоугольные области

19

Функция L(x1, x2…, xn) называется ограниченной сверху (снизу) на множестве M Rn, если существует число К такое, что для всех (x1, x2,…, xn) из множества М выполняется неравенство L(x1, x2,…, xn) ≤ К (L(x1, x2,…, xn) ≥ К). Функция, ограниченная и сверху, и снизу, называется ограниченной.

Будем говорить, что целевая функция ЗЛП ограничена, если в задаче на максимум она ограничена на допустимом множестве сверху, а в задаче на минимум — снизу.

Теорема 2. Если в задаче линейного программирования допустимое
множество отлично от пустого и целевая функция ограничена, то суще-
ствует по крайней мере одно оптимальное решение.
			Точку выпуклого множества,
Y2			не	являющуюся выпуклой ли-
			нейной		комбинацией		никаких
		Z2
			других его точек, называют угло-
Y
		Z	вой	(или вершиной). Иллюстра-
		Z1	цией может служить рис. 4.
Y1			У выпуклого множества, изо-
			браженного на рис. 4, точки X
	X	W	и W являются его вершинами,
Рис. 4. Вершины выпуклого множества			а точки Y и Z — нет. Действи-
			тельно, каждая из двух послед-
			них	точек		является	выпуклой
линейной комбинацией других его точек: Y, например, является выпуклой
линейной комбинацией точек Y1 и Y2, а Z — выпуклой линейной комбина-
цией Z1	и Z2 (см. замечание 5). У X и W таких точек нет.
Теорема 3. Если в задаче линейного программирования целевая функ-

ция L(X) ограничена на допустимом множестве Х, то угловая точка, в которой L(X) принимает наибольшее (наименьшее) значение среди всех угловых точек этого множества, является оптимальным решением данной задачи.

Эта теорема дает возможность разработать алгоритм, позволяющий решить ЗЛП методом перебора вершин. Для чего

первое, что необходимо сделать, — это определить все угловые точки допустимого множества;

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

20