Матан_ЛинПрог

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К РЕШЕНИЮ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Составители: к.ф.-м.н., ст. преподаватель кафедры математики и методов моделирования З.Р.СУЛЕЙМЕНОВА ст. преподаватель кафедры математики и методов моделирования К.С.САГИНДЫКОВА

к.ф.-м.н., ст. преподаватель кафедры математики и методов моделирования Н.К.СЫЗДЫКОВА ст. преподаватель кафедры математики и методов моделирования Е.Т.ОРАЗГАЛИЕВ

Рецензенты: к.ф.-м.н., доцент кафедры математики и методов моделирования Т.У Аубакиров

к.т.н., профессор кафедры высшей математики КарГТУ Н.Адильбеков

Введение

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

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

f (x1,x2,...,xn )

при условиях g(x1,x2,...,xn ) bi , (i 1,m), где f и gi заданные функции, а bi

–некоторые действительные числа.

Взависимости от свойств функций f и gi математическое

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

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

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

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

экономический анализ, расширить область экономической информации,

интенсифицировать экономические расчеты.

Можно выделить пять основных этапа проведения экономико-

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

а) постановка задачи;

б) построение математической модели;

в) решение с помощью модели поставленной задачи;

г) проверка адекватности модели реальной действительности и ее корректировка в случае недостаточной степени соответствия модели реальному процессу;

д) реализация результатов исследования.

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

Построение математических моделей экономических задач

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

F c1x1 c2x2 ... cnxn max min

(1.1)

при условиях:

a11x1 a12x2 ...

a1nxn b1

a

x a

22

x

2

...

a

2n

x

n

b

21 1

2

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

aknxn bk

(1.2)

ak1x1 ak2x2 ...

a

k 1,1

x a

k

1,2

x

2

...

a

k 1,n

x

n

b

1

k 1

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

am2x2

amnxn bm

am1x1

xj

0

( j

1,l

, l

n),

(1.3)

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

Система (1.2) называется системой ограничений, а линейная функция

(1.1) – целевой функцией.

Краткая запись задачи линейного программирования:

n
F cjxj max min								(1.4)
j 1
при ограничениях:
n
	bi ,	(i 1,k)
aijxj
j 1								(1.5)
n
aijxj	bi ,	(i					)
					k 1,m
j 1
xj 0	( j		; l n)					(1.6)
		1,l

Вектор X (x1,x2,...,хn ), удовлетворяющий ограничениям (1.5), (1.6),

называется допустимым решением (планом).

План X* (x1 ,x2,...,хn ), при котором целевая функция (1.4) принимает максимальное или минимальное значение, называется оптимальным.

Если система ограничений (1.5) состоит лишь из одних неравенств, то такая форма задачи линейного программирования называется стандартной (симметричной); если система ограничений (1.5) состоит лишь из одних уравнений, то такая форма задачи линейного программирования называется

канонической (основной).

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

Вводя дополнительные переменные xn i 0, i l 1,...,m, ограничениянеравенства из (1.2) можно записать в виде равенств:

n

aij xj xn i bi , i l 1,...,m

j 1

Если в системе ограничений заданы неравенства со знаками «≥», то соответствующие дополнительные переменные следует вводить со знаком «- ».

Задачу минимизации функции Fmin c1x1 c2x2 ... cnxn можно свести к задаче максимизации функции, умножив на «-1»:

	Fmax Fmin c1x1 c2x2		... cnxn .
Часто используется векторная запись задачи:
F(x) C X max min			(1.7)
при
x1P1 x2P2	... xnPn В,		(1.8)
X 0,			(1.9)
где X (x1,...,xn)	– вектор	неизвестных,	C (c1,...,cn) – вектор
коэффициентов целевой функции		f (x); P1,P2,...,Pn,В, – m-мерные вектор-

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

	b				a				a
		1			11				12
В	b			, P	a	21		, P	a	22
		2
				1				2
	...				...				...
	b				a	m1			a	m2
		m

			a
			1n
,...,P			a2n		,
	n
			...
			amn

X 0 – краткая форма записи условий неотрицательности переменных xj .

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

1. Задача использования сырья

Пусть xj	( j 1,n) – число единиц продукции Pj , запланированной к
производству;	bi (i		)	– запас сырья Si ; aij (i		, j		) – число
		1,m			1,m		1,n

единиц сырья Si , затрачиваемого на изготовление единицы продукции Pj ; cj

( j 1,n) – прибыль от реализации единицы продукции Pj .

Тогда экономико-математическая модель задачи об использовании сырья в общей постановке примет вид:

найти такой план X (x1,x2,...,xn ) выпуска продукции, при котором целевая функция принимает максимальное значение:

Fmax c1x1 c2x2

... cnxn

(1.10)

и который удовлетворяет условиям:

a11x1

a12x2

... a1nxn

b1

a22x2

... a2nxn

b2

a21x1

(1.11)

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

a

x

a

m2

x

2

... a

mn

x

n

b

m

m1 1

x1 0,x2 0,...,xn

0

(1.12)

2. Задача составления рациона

Пусть

xj

( j

) –

число

единиц корма

j-го вида; bi (i

) –

1,n

1,m

необходимый минимум содержания в рационе питательного вещества Si; aij

(i 1,m, j 1,n) – число единиц питательного вещества Si в единице корма j-го вида; cj ( j 1,n) – стоимость единицы корма j-го вида.

Тогда экономико-математическая модель задачи на составление

рациона в общей постановке примет вид:

найти

такой рацион

X (x1,x2,...,xn ), при

котором целевая функция

принимает минимальное значение:

Fmin c1x1

c2x2 ... cnxn

(1.13)

и который удовлетворяет условиям:

a11x1

a12x2

... a1nxn

b1

a22x2

... a2nxn

b2

a21x1

(1.14)

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

a

x

a

m2

x

2

... a

mn

x

n

b

m

m1 1

x1 0,x2 0,...,xn

0

(1.15)

3. Транспортная задача

Пусть

cij (i

,

j

)

-

тарифы перевозки единицы груза из i -го

1,m

1,n

пункта отправления в

j-ый пункт назначения; ai

(i

) - запасы груза в i-

1,m

том пункте отправления;

bj ( j

)

- потребности в грузе в j-ом пункте

1,n

назначения; xij

(i

, j

) - количество единиц груза, перевозимого из

1,m

1,n

i-го пункта отправления в

j-ый пункт назначения.

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

Fmin	c11x11 c12x12 ... c1nx1n c21x21 c22x22	...
	c2nx2n ... cm1xm1 cm2xm2 ... cтnxтn	(1.16)

при условиях:

x11		x12		... x1n a1
		x22		... x2n			a2
x21
...............................
		xm2 ... xmn am
xm1
x		x	21	... x	m1		b
	11						1
x		x		... x		m2	b
	12		22				2
...............................
x		x	2n	... x		mn	b
	1n						n

x11 0,...,x1n 0,x21 0,...,x2n 0,...,xm1 0,...,xmn 0

Рассмотрим на примерах.

1. Задача использования сырья

(1.17)

(1.18)

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

	КОЛ-ВО ЕД. СЫРЬЯ НА
ВИД	ИЗГОТОВЛ. ЕД.		ЗАПАСЫ
СЫРЬЯ	ПРОДУКЦИИ		СЫРЬЯ
	Р1	Р2
S1	2	3	21
S2	1	1	8
S3	2	0	10
ПРИБЫЛЬ
ОТ ЕД.	30	20
ПРОДУКЦ

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

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

2x		3x		21
	1		2		,
x1	x2 8
2x		10
	1

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

быть наложено ограничение неотрицательности: x1 0, x2 0. Конечная цель задачи – получение максимальной прибыли при реализации продукции: f 30x1 20x2 max .

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

f 30x1 20x2 max

	2x1			3x2				21
	x		x			2	8
при		1						.
	2x			10
			1
	x		,x		2	0
		1

2. Задача составления рациона

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

		КОЛ-ВО		НЕОБХОД.
ПИТАТЕЛЬ-	ПИТАТЕЛЬНЫХ			КОЛ-ВО
НЫЕ	ВЕЩЕСТВ В 1КГ.			ПИТАТЕЛЬНЫХ
ВЕЩЕСТВА		КОРМА		ВЕЩЕСТВ
	Корм I		Корм II
S1	2		1	4
S2	1		3	6
S3	1		0	1
СТОИМОСТЬ
1 КГ КОРМА	4		1

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

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

2x1 x2 4

x1 3x2 6

x1 1

x1 0,x2 0

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

Таким образом, экономико-математическая модель задачи:

f	4x1 x2 min
	2x1 x2		4
		3x2	6
при	x1
	x	1		.
	1
	x	0,x	2	0
	1

3. Транспортная задача

На три базы A1,A2, A3, поступил однородный груз в количествах соответственно равных 50, 30 и 10 единиц. Этот груз требуется перевезти в четыре пункта назначения B1,B2,B3,B4 соответственно в количествах 30, 30, 10 и 20 единиц. Тарифы перевозок единицы груза даны в таблице.

ПУНКТЫ	ПУНКТЫ НАЗНАЧ.				ЗАПАСЫ
ОТПРАВЛ.	В1	В2	В3	В4	ГРУЗА
A1	1	2	4	1	50
A2	2	3	1	5	30
A3	3	2	4	4	10
ПОТРЕБН.
В ГРУЗЕ	30	30	10	20

Найти оптимальный план перевозок данной транспортной задачи.

Пустьxij (i 1,3, j 1,4) - количество единиц груза, перевозимого из i-го пункта отправления в j-ый пункт назначения. Тогда экономикоматематическая модель задачи:

Fmin 1 x11 2 x12 4 x13 1 x14 2 x21 3 x22 1 x23 5 x24

3 x31 2 x32 4 x33 4 x34

при условиях:

	x11	x12		x13 x14						50
		x22		x23				x24		30
	x21
	x31	x32		x33				x34		10
		x21 x31 30
	x11
	x	x	22	x		32		30
	12
	x13	x23		x33				10
	x	x	24	x		34		20
	14
		0	(i 1,3;					j 1,4)
	xij
		Упражнения
	Составить экономико-математические модели следующих задач.
	1.1 Завод выпускает изделия двух типов: Р1									и Р2 . При этом используется

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

		СЫРЬЕ			ПРИБЫЛЬ
ИЗДЕЛИЯ	I	II	III	IV	ОТ ЕД-ЦЫ
					ИЗД.
Р1	2	1	0	2	3
Р2	3	0	1	1	2
ЗАПАСЫ
СЫРЬЯ	21	4	6	10

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

1.2 На заводе используется сталь трех марок: A, B и C, запасы которых соответственно равны 10, 16 и 12 ед. Завод выпускает два вида изделий. Для изготовления единицы изделия I требуется по одной единице стали трех марок. Для единицы изделия II требуется 2 единицы стали марки B, одна – марки C и не требуется сталь марки A. От реализации единицы изделия вида I завод получает 3 тенге прибыли, вида II – 2 тенге. Составить план выпуска продукции, дающий наибольшую прибыль.

1.3 Фабрика выпускает три вида тканей. Суточные ресурсы фабрики следующие: 700 ед. производственного оборудования, 800 ед. сырья и 600 ед. электроэнергии, расход которых на единицу ткани представлен в таблице:

РЕСУРСЫ		ТКАНИ
	I	II	II
Оборудование	2	3	4
Сырье	1	4	5
Электроэнергия	3	4	2

Цена одного метра ткани I – 8 тенге, ткани II – 7 и ткани III – 6 тенге. Сколько надо произвести ткани каждого вида, чтобы прибыль от реализации была наибольшей?