Тема 2. Методы и задачи линейного программирования

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

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

Вкачестве методов оптимизации в экономике находят применение все основные разделы математического программирования (планирования): линейное, нелинейное и динамическое.

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

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

целевой функцией.

Ограничения характеризуют имеющиеся возможности решения задачи.

Вобщем виде математическая модель задачи линейного программирования (ЛП) записывается так:

F(x)= c1x1 + c2x2 +L+ c j x j +L+ cn xn → max(min)

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

a11x1

+ a12 x2

+L+ a1 j x j

+L+ a1n xn = b1

a

x

+ a

22

x

2

+L+ a

2 j

x

j

+L+ a

2n

x

n

≤ b

21 1

2

LLL

x

+L+ a

x

+L+ a

x

≥ b

a

x + a

i 2

2

ij

j

in

n

i1 1

i

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

+L+ a

x

+L+ a

x

= b

a

x

+ a

x

2

mj

j

mn

n

m1 1

m

2

m

x j ≥ 0, i =

1, m

,

j =

1, n

где хj – искомые величины, содержащие решение поставленной задачи;

аij , bi , c j – заданныепостоянныевеличины, характеризующиеусловиязадачи.

Вектор Х = {х1 , х2 ,..., хn }, удовлетворяющий системе ограничений, называ-

ется допустимым планом.

Допустимый план, составляющий оптимум целевой функции, называется

оптимальным планом.

11

Классификация моделей ЛП

Различают следующие типы моделей:

1. Основная:

max F(x) =	n	c		x		(1)	X :	n			≤ b ,(i
	∑		j		j				a x	j
									∑ ij		i
	j=1
								j=1

=1, m); x j ≥ 0,(j =1, n) (2)

Существует симметричная форма записи основной задачи ЛП:

n

min f (x) = ∑c j x j (3)

j=1

X :	n			≥ b ,(i
		a x	j
		∑ ij		i
	j=1

=1, m); x j ≥ 0,(j =1, n) (4)

2. Каноническая:

Получается из основной, если в системе ограничений используются ограничения в виде равенств. Используя (1) и (2) запишем каноническую задачу в координатной форме.

n	n
max F(x) = ∑c j x j (1)		∑aij x j
	X :
j=1
	j=1

= b ,(i =1, m); x			j	≥ 0,(j =1, n)			(5)
i

3. Каноническая в базисной форме.

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

Переменные, обладающие следующим свойством: любая из таких переменных входит с коэффициентом «1» только в одно из уравнений системы, а в другие уравнения – с коэффициентом «0», называются базисными переменными.

Пусть базисными являются х1 , х2 ,..., хm , тогда

n		n
max F(x) = ∑c j x j (1)		∑aij x j
	X : xi +
j=1		j=m+1

= bi ,(i =1, m); x j ≥ 0,(j =1, n) (6)

Замечание: каноническая модель в базисной форме ((1), (6)) является основой алгебраического метода решения задач ЛП, который носит название сим-

плекс-метод.

4. Общая модель.

Общая модель ЛП – обобщение всех вышеописанных моделей.

n

a

x

≤ b

,(i =

);

x

ij

j

1, k

j

∑

i

j=1

≥ b ,(i =

);

max F(x) =

n

c

x

(1)

X :

n

a

x

j

j

ij

j

k +1, r

min

∑

∑

i

j=1

j=1

n

= bi ,(i =

);

∑aij x j

r +1, m

j=1

≥0,(j =1, l)

xj ≤ 0,(j = l +1, s)

xj ≥≤ 0,(j = s +1, n

(7)

)

12

Взаимосвязь моделей ЛП. Эквивалентные преобразования

Рассмотрим возможность перехода от общей, основной и канонической к канонической в базисной форме.

1. Рассмотрим основную модель ЛП (1)-(4): чтобы перейти к канонической модели в базисной форме, необходимо преобразовать неравенства в системе ограничений (2),(4) в равенства таким образом, чтобы были выделены базисные переменные (принцип весов). Для этого добавим (если знак ≤) или вычтем (если знак ≥) из левой части каждого ограничения (2) дополнительную переменную так, чтобы реализовалось равенство. Пусть это переменные х1 , х2 ,..., хm , тогда

система ограничений имеет вид:

n						,
X : ∑aij x j + xn+i = bi ,(i =1, m);			x j ≥ 0,(j =1, n)
j=1
xn+i −базисная переменная.

2.Если в исходной задаче целевая функция исследуется на min f (рассматривается симметричная форма), то для того, чтобы перейти к задаче на max F, необходимо ввести в рассмотрение функцию F= - f. Тогда поиск min f эквивалентен поиску max F, причем min f = max F.

3.Если в системе ограничений (7) хj – любого знака, то она представляется

как разность двух неотрицательных переменных:

х j = u j − v j ; u j , v j ≥ 0

Графический способ решения задач ЛП

Этот способ применяется для решения задач с двумя переменными (n = 2) или задач, сводящихся к таким.

Утверждение 1. Прямая l: Ах + Ву = С делит числовую плоскость Оху на две полуплоскости, в одной из которых Ах + Ву < С, в другой Ах + Ву > С.

Пример 1. Определить полуплос-		y
кость, в которой 2х+5у<10.		l
Строим	граничную прямую l:
2х+5у=10. Берем точку О (0,0), под-		2	l: 2x + 5y = 10
ставляем ее в неравенство. Получаем
0+0<10, то есть 0<10 это верно. Значит
мы заштриховываем полуплоскость, в
которой лежит точка О (0,0). В нашем			5	x
случае это	полуплоскость, лежащая		Рис. 2.1.1. Определение
ниже прямой (рис. 2.1.1).
			полуплоскости

Утверждение 2. Пусть l: Ах + Ву = С. Вектор n =(А, В), перпендикулярный

кпрямой l называется вектором-нормалью. Прямая l1: Ах + Ву = С1 параллельна

кпрямой l и получена перемещением прямой l по направлению векторанормали, если С1>C; и в направлении (- n ), если С1 < C.

13

Пример 2. Рассмотрим прямую из примера 1 и построим для нее векторнормаль и параллельные ей прямые. Вектор-нормаль n имеет координаты (2, 5). Прямая l1: 2х + 5у = 3 лежит ниже исходной прямой l: 2х + 5у = 10, т.к. 3 < 10. Прямая l2: 2х + 5у = 20 лежит выше исходной прямой l : 2х + 5у = 10, т.к. 20 > 10 (рис. 2.1.2).

y

n (2;5)

l2 х

l1 l

Рис. 2.1.2. Построение вектора-нормали

Рассмотрим задачу ЛП в следующем виде:

F ( x1 ; х2 ) = с1 х1 + с2 х2 → max (min )
n
	≤ bi ,(i = 1, m ); x j
				≥ 0,все или некоторые
X : ∑ a ij x j
j =1

Алгоритм графического метода:

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

1.Составляем уравнение граничных прямых, заменяя в системе ограничений все неравенства на точные равенства.

2.Строим прямые на числовой плоскости, заштриховывая те полуплоскости, в которых выполняются нужные неравенства.

3.Пересечение полуплоскостей и дает множество допустимых планов.

IIэтап. Построение оптимального плана.

1.Строим вектор-нормаль n = (с1; с2 ) , координаты которого есть коэффи-

циенты при переменных в целевой функции.

2.Через произвольные точки множества допустимых планов проводим прямую l n .

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

14

При решении задач на min прямую l перемещают в противоположном направлении вектора-нормали (- n ) до крайнего положения, пока она имеет общие точки с множеством допустимых планов.

Если окажется, что прямая l параллельна одной из граничных прямых, то в этом случае экстремум достигается во всех точках из отрезка соответствующей граничной прямой, а задача ЛП имеет множество решений. Такая задача имеет альтернативный оптимум, ее решение осуществляется по формуле:

Хопт = (1−t)X1 +tX2, где0 ≤ t ≤1, X1, X2 – оптимальные решения в угловых точках ОДП у этой прямой.

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

Пример 3. Задача о составлении рациона.

При откорме каждое животное ежедневно должно получать не менее 9 ед. питательного вещества S1, не менее 8 ед. питательного вещества S2 и не менее 12 ед. вещества S3. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 2.1.3.

		Таблица данных № 1		Таблица 2.1.3
				Ежедневная
	Питательные	Содержание пит. веществ в ед. продукта
				потребность в пит.
	вещества	Корм 1	Корм 2
				веществах
	S1	3	1	9
	S2	1	2	8
	S3	1	6	12
	Стоимость ед.	4	6
	продукта

Составить дневной рацион необходимой питательности, имеющий минимальную стоимость.

Решение:

Обозначим через x1 и x2 количество килограммов корма 1 и 2 в дневном ра-

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

3x1 + x2 ≥ 9x1 + 2x2 ≥ 8x1 +6x2 ≥12

x1, x2 ≥ 0

15

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

f (x1; х2 ) = 4х1 +6х2 → min

I этап. Построим многоугольник решений (рис. 2.1.3). Для этого в системе координат х1Ох2 на плоскости изобразим граничные прямые:

3x			+ x	2	= 9		(l )
		1					1
x1		+ 2x2 = 8 (l2 )
x		+ 6x		2	=12		(l )
	1						3
x		= 0, x			2	= 0
	1

X2

A
9
			N(4,6)
4		B
2
			C	D
0		3	8	12
	L	l1		l3	X1
				l2

Рис. 2.1.3. Графическое построение решения

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

II этап. Для построения прямой 4х1 +6х2 =0 строим вектор-нормаль n =(4; 6) и через точку О (0,0) проводим прямую, перпендикулярную ему. Построенную прямую перемещаем параллельно самой себе в направлении вектора n . Из рис. 2.1.3 следует, что она впервые коснется многогранника решений в угловой точке В. Если прямую перемещать дальше в направлении вектора n , то значения линейной функции возрастут, значит в точке В наша целевая функция принимает минимальное значение.

16

Точка В лежит на пересечении прямых l1 и l2 . Для определения ее коорди-

нат решим систему уравнений:
3x1 + x2 = 9		(l1)
x	+ 2x = 8	(l )
1	2	2

Получаем: х1 = 2, х2 = 3. Подставляя значения x1 и x2 в целевую функцию,

получаем f (x1 ; х2 )min = 4 ×2 + 6 ×3 = 26 .

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

Пример 4. Задача использования сырья.

Для изготовления двух видов продукции Р1 и Р2 используют три вида сырья: S1, S2, S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1.4.

			Таблица 2.1.4
	Таблица данных № 2
		Количество ед. сырья,
Вид сырья	Запас сырья	идущих на изготовление ед. продукции
		Р1	Р2
S1	20	2	5
S2	40	8	5
S3	30	5	6
Прибыль от ед.	продукции, руб.	50	40

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

Решение:

Обозначим через x1 количество единиц продукции Р1, а через x2 – количе-

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

2x1 +5x2 ≤ 20

8x1 +5x2 ≤ 405x1 +6x2 ≤ 30

x1 , x2 ≥ 0

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

Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных x1 и x2 . Реа-

лизация x1 единиц продукции Р1 и x2 единиц продукции Р2 дает соответственно 50 x1 и 40 x2 руб. прибыли, суммарная прибыль f (x1; х2 ) = 50х1 + 40х2 (руб).

17

Требуется найти такие x1 и x2 , при которых функция f (x1 ; х2 ) достигает

максимума, т.е. f (x1;х2 ) =50 х1 +40 х2 →mах. При заданных ограничениях:

2x		+		5x		≤ 20
	1				2
8x1 +5x2 ≤ 40
		+6x2 ≤ 30
5x1
x	, x		2	≥ 0
1
I этап. Построим многоугольник решений (рис. 2.1.4). Для этого в системе
координат х1Ох2 на плоскости изобразим граничные прямые:
2x1 +5x2 = 20							(l1)
8x		+5x				= 40	(l	)
	1			2			2	)
5x		+6x				= 30	(l
	1			2			3
x	= 0, x					= 0
1				2
X2

l2

8

7

6

l3

5

l1		А
	4
		n = (5 , 4 )
	3	В
	2	С
	1

O

1

2

3

4

5 D 6

Рис. 2.1.4. Построение решения

18

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

II этап. Для построения прямой 50х1 + 40х2 = 0 строим вектор-нормаль n = (50;40) =10(5;4), и через точку О (0,0) проводим прямую, перпендикулярную

ему. Построенную прямую перемещаем параллельно самой себе в направлении вектора n . Из рис. 2.1.4 следует, что последней точкой пересечения из опорного плана является точка С, где целевая функция принимает максимальное значение. Точка С лежит на пересечении прямых l2 и l3. Для определения ее координат решим систему уравнений:

8x1 +5x2 = 40					(l2 )
5x		+6x	2	= 30	(l	3	)
	1

Оптимальный план задачи: x1 = 90/23 = 3,9; x2 = 40/23 = 1,7. Подставляя

найденные значения в целевую функцию, получаем: f (x1; х2 )mаа = 50 3,9 + 40 1,7 = 260,3

Таким образом, для получения максимальной прибыли в размере 260,3 руб. необходимо запланировать производство 3,9 ед. продукции Р1 и 1,7 ед. продукции Р2.

Пример 5. Задача о раскрое.

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

Допустим перед нами листы дефицитного материала размером 6×13 м. Из каждого такого листа необходимо выкроить по несколько заготовок двух видов: заготовки А размером 5×4 м и заготовки Б размером 2×3 м. Задача заключается в том, чтобы получить как можно больше заготовок обоих видов с наименьшим количеством отходов. Кроме того, необходимо обеспечить комплектность заготовок: на 1 заготовку А должно приходиться 5 заготовок Б. Как вести раскрой?

Решение:

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

Способ раскроя № 1

Способ раскроя № 2

Б

Б

Б

Б

Б

А

А

А

А

А

Б

Б

19

Способ раскроя № 3

				Б	Б	Б
А
				Б	Б	Б
				Б	Б	Б

Оказывается, что больше трех заготовок А с листа выкроить невозможно. Способ № 1: 3 заготовки А и 1 заготовка Б.

Способ № 2: 2 заготовки А и 6 заготовок Б. Способ № 3: 1 заготовка А и 9 заготовок Б.

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

Для составления оптимального плана раскроя материала построим график. По оси Х отложим количество заготовок А, а по оси Y – число заготовок Б

(рис. 2.1.5).

Число заготовок Б

9	N (1;5)

6

5

3

1

1 2 3

Число заготовок А

Рис. 2.1.5. График раскроя материала

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

Какой же план раскроя рационален? Этот план дает точка, лежащая на пересечении вектора-нормали с границей области допустимых планов – линией, соединяющей способы № 2 и № 3. Она находится посередине между упомянутыми способами. (Проверьте это самостоятельно). Итак, оптимальный план раскроя заключается в том, что половина листов кроится способом № 2, а половина – способом № 3.

20

Проверим наш оптимальный план на партии в 200 листов. Половину – 100 листов – раскроим по способу № 2 и получим 100 × 2= 200 заготовок А и 100 × 6 = 600 заготовок Б. Вторую половину листов по способу № 3 и получим 100 × 1 = 100 заготовок А и 100 × 9= 900 заготовок Б. Всего же получилось 300 заготовок А и 1500 заготовок Б – комплектность 1 к 5 соблюдена.

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

Симплексный метод

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

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

План называется опорным, если все базисные переменные имеют неотрицательное значение, а значение свободных переменных равно 0.

Алгоритм симплексного метода:

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

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

Для этого заполняем первую симплекс-таблицу (табл. 2.1.5). С экономической точки зрения, первый опорный план соответствует бездействию: выпуски продукции равны 0 (свободные переменные равны 0), резервы ресурсов совпадают с их запасами.

				Шаблон симплекс-таблицы						Таблица 2.1.5
сi		БП	с1	с2	…	сm		сm+1	…	сn	F(x)
			x1	x2	…	xm		xm+1	…	xn	bi
с1		x1	1	0	…	0		h1,m+1	…	h1n	b1
с2		x2	0	1	…	0		h2,m+1	…	h2n	b2
…		…	…	…	…	…		…	…	…	…
с		x	0	0	…	1		hm,m+1	…	h	b
m		m								mn	m
		j	0	0	…	0		m+1	…	n	F(x1 )
	Все строки первой таблицы заполняем по данным системы ограничений и
целевой функции, за исключением строки							j .

Индексная строка находится по формулам:

m

j = ∑ci hij −c j , (j =1,n)– для переменных

i=1

21

m

j = ∑cibi – для свободного члена

i=1

Критерий оптимальности. Если среди оценок j нет отрицательных, т.е. j ≥0, то опорный план является оптимальным, значения его базисных переменных находятся в столбце bi , значение свободных переменных равно 0. Оптимальное значение находится в клетке F(x1 ).

Если при этом все	j	> 0, то оптимальный план называется единственным.
Если хотя бы одна	j	= 0, то имеет место альтернативная оптимизация.
Если среди оценок	j	есть отрицательные, то оптимальный план не являет-

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

Если хотя бы один столбец, отвечающий отрицательной оценке j , цели-

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

IV этап. Построение нового базиса.

Среди отрицательных оценок j находим наибольшую по абсолютной ве-

личине. Пусть р	= max	j	. Столбец с № p называется ключевым столбцом.
	j < 0

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

Определяем вектор, который выводится из базиса. Для этого элементы столбца bi делим на положительные элементы ключевого столбца (0 и отрица-

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

V этап. Определение нового опорного плана.

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

С помощью строки « » получаем нули в ключевом столбце: для того, чтобы получить ноль в i-ой строке симплекс таблицы, нужно из старой i-ой строки вычесть строку « », умноженную на соответствующее число.

Возвращаемся к этапу I.

Пример 6. Предположим, что предприятие может выпускать четыре вида продукции (n = 4), используя для этого три вида ресурсов (m = 3). Известна технологическая матрица А затрат любого ресурса на единицу каждой продукции, вектор В объемов ресурсов и вектор С удельной прибыли:

	3	2	6	0			150
	4	2	3	5			130		С = (30 11 45 6)
А =						В =
	4	3	2	4			124

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

22

Решение:

Составим целевую функцию и запишем ограничения по ресурсам.

F (x1; х2 ; x3; x4 ) = 30х1 +11х2 + 45x3 + 6x4 → mаx

3x1 + 2x2 +6x3				≤150
4x		+ 2x	+3x	+5x	≤130
	1	2	3	4
4x		+3x	+ 2x	+ 4x	≤124
	1	2	3	4
x	≥ 0,x		≥ 0,x	≥ 0,x		≥ 0
							,
1		2	3	4

где x j – выпуск продукции Pj (j =1,4).

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

x5 , x6 , x7 – остатки ресурсов определенного вида (неиспользуемое количе-

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

Тогда вместо системы неравенств получим систему уравнений:

3x1 + 2x2 + 6x3									+ x5						= 150
4x				+ 2x		2	+ 3x	+ 5x	4			+ x	6			= 130
		1					3
4x				+ 3x		2	+ 2x	+ 4x	4				+ x	7		= 124
		1					3
x			≥ 0,x		2		≥ 0,x	≥ 0,x		4	≥	0,x	≥ 0,x		6	≥ 0,x	≥ 0
	1						3					5					7

Воспользуемся тем, что правые части всех уравнений этой системы неотрицательны, а введенные переменные являются базисными. Приравняв к нулю свободные переменные x1 ,x2 ,x3 , х4 , получаем базисное неотрицательное решение:

x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 =150, x6 =130, x7 =124.

Первые четыре компоненты представляют собой производственную программу x = (0,0,0,0 ) , по которой пока ничего не производится.

Составим первую симплексную таблицу (табл. 2.1.6):

							Симплекс-таблица № 1													Таблица 2.1.6
	сi	БП	30	11	45	6	0	0	0	bi						Пояснения
			x1	x2	x3	x4	x5	x6	x7
	0	x5	3	2	6	0	1	0	0	150	max (|-30|, |-11|, |-45|, |-6|) = 45,
											x3 – в базис. Третий столбец – ключевой.
	0	x6	4	2	3	5	0	1	0	130
												150		130				124		150
	0	x7	4	3	2	4	0	0	1	124	min (		;			;			) =		= 25.
											6			3			2		6
			-30	-11	-45	-6	0	0	0	0
		j									x5 – из базиса. Первая строка – ключевая.

23

Индексная строка находится по формулам:

	m
	= ∑ci hij −c j , (j =		)– для переменных
j		1,4
	i=1
	m
j	= ∑cibi – для свободного члена
	i=1
1 = (0×3 + 0×4 + 0×4) − 30 = −30;				2 = (0×2 + 0×2 + 0×3) − 11= −11;
3 = (0×6 + 0×3 + 0×2) − 45= −45;				4 = (0×0 + 0×5 + 0×4) − 6= −6;
5 = 0; 6 = 0; 7 = 0 .

Проверяем критерий оптимальности: в индексной строке j имеются четы-

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

III этап. Проверка целевой функции на неограниченность.

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

IV этап. Построение нового базиса.

Среди отрицательных оценок j находим максимальную по абсолютному значению. Это будет j = −45. Обоснуем этот выбор с экономической точки

зрения: наиболее выгодно начинать производить продукцию третьего вида, т.к. прибыль на единицу этой продукции наибольшая.

Следовательно, третий столбец – ключевой. В симплекс-таблице этот столбец заштрихован. Переменную x3 вводим в базис.

Определим переменную, которую нужно вывести из базиса. Для этого составим отношения и выберем из них минимальное:

		b				150			130			124				150
min			i		= min			;			;				=			= 25
			> 0			6			3			2				6
a		i3

Это отношение соответствует первой строчке в симплекс-таблице, она и будет ключевой строкой. Она тоже заштрихована. Следовательно, из базиса выводим переменную x5 . Получили новый базис ( x3 , x6 , x7 ).

V этап. Определение нового опорного плана.

Ключевое число 6. Найдем элементы строки, которая обозначается « »: (1/2, 1/3, 1, 0, 1/6, 0, 0, 25). Эти числа получаются делением каждого элемента ключевой строки на ключевое число. Эта строка будет первой во второй сим- плекс-таблице, которую нужно заполнить.

Так как переменная x3 базисная, то только в одной ячейке у нее должно

быть единичное значение, а в других – нулевое.

С помощью строки « » зануляем числа 3 и 2 в третьем столбце. Для этого строчку « » умножаем на (-3) и на (-2) и складываем со второй и третьей. Результат записываем во вторую симплекс-таблицу (табл. 2.1.7), во вторую и третью строчки.

Находим оценки j .

24

											Симплекс-таблица № 2																Таблица 2.1.7
сi		БП				30	11	45		6		0		0		0	bi					Пояснения
						x1	x2	x3		x4		x5		x6		x7
45			x3			½	1/3	1		0		1/6		0		0	25*	max (|-15/2|,|-6|)=15/2,
																		x1 – в базис. Первый столбец – ключевой.
0			x6			5/2	1	0		5		-1/2		1		0	75
																		25		55				74	)=	55		=25.
																		min (		;			;
																			1		5			3		5
0			x7			3	7/3	0		4		-1/3		0		1	74
																		2		2						2
																		x6 – из базиса. Вторая строка – ключевая
				j		−152	4	0		-6		−152		0		0	1125
1 = (45×1/2 + 0×5/2 + 0×3) − 30 = −15/2;																	2 = (45×1/3 + 0×1 + 0×7/3) − 11 = 4;
3 = (45×1 + 0×0 + 0×0) − 45 = 0;														4 = (45×0 + 0×5 + 0×4) − 6 = −6;
5	= (45×1/6 + 0×( −1/2) + 0·(−1/3)) − 0 = 15/2;																	6 = 0;		7 = 0 .
		Значение функции F(x) = 45×25 + 0×55 + 0×74 = 1125.
		Каждый элемент симплексной таблицы имеет определенный экономиче-
ский смысл. Например, во второй симплексной таблице:
		• в столбце x1 :
	1				– показывает,					на	сколько				следует уменьшить изготовление товаров

2

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

52 ;3 – показывают, сколько потребуется сырья второго и третьего вида при

включении в план одного изделия первого вида.

Таким образом, при включении в план одного изделия первого вида, потребуется уменьшение выпуска продукции третьего вида на 0,5 единиц, а также дополнительные затраты 2,5 единицы сырья второго вида и 3 единиц сырья третьего вида, что приведет к увеличению прибыли предприятия на 7,5 денежных единиц;

• в столбце x5 :

1/6; −1/2; −1/3 – показывают, что увеличение объема сырья первого вида на единицу позволило бы увеличить выпуск продукции третьего вида на 1/6, что одновременно потребовало бы 1/2 единицы второго сырья и 1/3 единицы третьего вида.

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

Среди отрицательных j находим максимальную по абсолютной величине.

Проделываем со второй симплексной таблицей то же, что и с первой. Получаем новую третью симплекс-таблицу (табл. 2.1.8).

25

Таблица 2.1.8

Симплекс-таблица № 3

	сi	БП	30	11	45	6	0	0	0	bi		Пояснения
			x1	x2	x3	x4	x5	x6	x7
	45	x3	0	2/15	1	-1	4/15	-1/5	0	14
	30	x1	1	2/5	0	2	-1/5	2/5	0	22	Все	j ≥0
	0	x7	0	17/15	0	-2	4/15	-6/5	1	8
		j	0	7	0	9	6	3	0	1290

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

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

x1 = 22, x2 = 0, x3 = 14, х4 = 0 ,

которая обеспечивает предприятию наибольшую возможную прибыль:

F(x) =30х1 +11х2 +45x3 +6x4 =30×22+11×0 +45×14+6×0 = 660+630 =1290

При этом первый и второй ресурсы будут использованы полностью, т.е. первый и второй ресурсы образуют «узкие места производства».

Вопросы для самоконтроля

1.В чем заключается основная задача методов оптимизации?

2.Особенности линейного программирования.

3.Объясните экономический смысл системы ограничений и целевой функции.

4.Назовите основные типы экономических задач, решаемых методами линейного программирования.

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

6.Объясните на примере алгоритм графического метода.

7.В чем заключается симплекс-метод?

8.К какой модели нужно привести задачу ЛП, чтобы ее можно было решить симплекс-методом. Как это сделать?

9.Что такое альтернативная оптимизация?

Задачи

Задача 1. Планируем производство металлообработки: стали и цветного металла. Станки, обрабатывающие металл, могут быть обыкновенные и с ЧПУ. За день обычный станок может обработать 200 кг стали и 200 кг цветного металла. Дневная прибыль от работы обычного станка составляет 1000 руб. Станок с ЧПУ за этот же день может обработать 700 кг стали и 100 кг цветного металла, прибыль от такого станка будет 5000 руб. Дневной запас стали − 46 000 кг, а за-

26

пас цветного металла − 22 000 кг. Производственная площадь позволяет вместить больше 80 станков. Сколько станков каждого типа должно работать в цехе, чтобы прибыль от работы станков была максимальной, если дневная прибыль от работы обычного станка составит 1000 руб., а от станка с ЧПУ – 5000 руб.?

Задача 2. Решите задачу ЛП:

f (x1 , x2 )= x1 + 53 x2 → min (max )3x1 + 5x2 ≥ 20

2x1 + x2 ≤ 23− x1 + 5x2 ≤ 38− 2x1 + x2 ≤ 4

x , x ≥ 0

1 2

Задача 3. Решите задачу ЛП:

f (x1, x2 , x3 , x4 )=8x1 −4x2 +2x3 −2x4 →max

x1 −x2 +4x3 −2x4 =23x1 +2x2 −x3 +4x4 =3

x1, x2 , x3 , x4 ≥0

Задача 4. Решите задачу ЛП:

f (xj )=16x1 +x2 −x3 −5x4 −5x5 →min(max)

2x1 +x2 +x3 =20−2x1 +3x2 +x4 =122x1 +4x2 −x5 =16

xj ≥0

Задача 5. Фирма «Морские прогулки» может приобрести большие катера вместимостью 18 человек и быстроходные катера вместимостью 5 человек. Быстроходный катер стоит 1100 $, большой катер – 1000 $. Фирма может потратить на покупку 165 000 $ и ожидать, что желающих покататься будет не меньше 900 человек. Сколько больших катеров и быстроходных катеров должна приобрести фирма, чтобы получить максимальный доход, если билет на быстроходный катер стоит 5 $, а на большой катер − 1,5 $ и фирма уже договорилась приобрести не менее 50 быстроходных катеров?

Задача 6. Для производства 4-х видов продукции используется 3 вида ресурсов. Данные представлены в таблице данных № 3 (табл.2.1.9).

		Таблица данных № 3				Таблица 2.1.9
Продукт,	Расход ресурса на производство ед.			продукции		Запасы
ресурс	P1	P2	P3		P4
S1	1	0	2		1	180
S2	0	1	3		2	210
S3	4	2	0		4	800
Прибыль	9	6	4		7

27

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

Задача 7. Фирма выпускает четыре пользующихся спросом изделия, причем месячная программа выпуска составляет 10 изделий типа 1 и 3, 200 изделий типа 2 и 120 изделий типа 4. Нормы затрат сырья на единицу различных типов изделий и прибыль от реализации 1 изделия приведены в таблице данных № 4 (табл. 2.1.10).

			Таблица данных № 4				Таблица 2.1.10
Вид сырья		Нормы затрат на одно изделие					Запасы
	P1		P2	P3		P4
1	5		1	0		2	1000
2	4		2	2		1	600
3	1		0	2		1	150
Прибыль	6		2	2,5		4

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

Задача 8. Стандартом предусмотрено, что октановое число автомобильного бензина А-76 должно быть не меньше 76, а содержание серы − не более 0,3%. Для изготовления такого бензина используется смесь четырех компонентов, данные которых приведены в таблице данных № 5 (табл. 2.1.11). Определить, сколько тонн каждого компонента следует использовать для получения 100 т бензина А-76, чтобы его стоимость была минимальной.

	Таблица данных № 5				Таблица 2.1.11
Характеристика		Компоненты бензина
	№1	№2		№3	№4
Октановое число	68	72		80	90
Содержание серы (%)	0,35	0,35		0,3	0,2
Ресурсы (т)	700	600		500	300
Себестоимость (у.е.)	40	45		60	90

Задача 9. Фирма, выпускающая трикотажные изделия, использует для производства продукции два вида сырья. Необходимые данные приведены в таблице данных № 6 (табл. 2.1.12).

Таблица 2.1.12

Таблица данных № 6

	Сырье	Запасы	Затраты на ед. продукции
		сырья
			Свитер	Жилет	Костюм
	Чистая шерсть	160	0,4	0,2	0,8
	Акрил	60	0,2	0,1	0,2
	Прибыль за изделие		16	15	22

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

28