Егоров, Казаков Мет. по лин. програм

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНДУСТРИАЛЬНЫЙ УНИВЕРСИТЕТ

О.П. Егоров О.Л. Казаков

Линейная алгебра и математическое программирование для экономистов

Часть 2. Математическое программирование

УЧЕБНОЕ ПОСОБИЕ

Москва 2004

2

Содержание

Предисловие 1. Линейное программирование

1.1.Задача линейного программирования

1.1.1.Задача об ассортименте продукции

1.1.2.Задача составления смеси (о диете)

1.1.3.Задача о раскрое

1.1.4.Задача о сменно-суточном планировании работы

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

Вопросы для самопроверки

1.3.Графическое решение задачи линейного программирования

Вопросы для самопроверки

Задания для самостоятельной работы

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

1.4.1.Улучшение оптимального решения за счет изменения дефицитного

ограничения

1.4.2.Изменение недефицитного ограничения без изменения оптимального решения

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

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

Вопросы для самопроверки Задания для самостоятельной работы

1.5.Каноническая форма представления области решений задачи линейного программирования

Вопросы для самопроверки

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

Задания для самостоятельной работы

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

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

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

1.8.2.Взаимно двойственные задачи линейного программирования и их свойства Вопросы для самопроверки

Задания для самостоятельной работы

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

1.10.Решение транспортной задачи

1.10.1.Определение начального решения

1.10.2.Нахождение вводимой в базис переменной

1.10.3.Нахождение выводимой из базиса переменной

2. Целочисленное линейное программирование

2.1.Задачи целочисленного линейного программирования

2.2.Метод ветвей и границ

Вопросы для самопроверки

Задания для самостоятельной работы

2.3. Метод отсечений (Гомори)

Вопросы для самопроверки Задания для самостоятельной работы

3. Динамическое программирование

3.1.Задача динамического программирования

3.2.Метод решения задач динамического программирования

3.3.Решение задачи линейного программирования методом динамического программирования

Вопросы для самопроверки Задания для самостоятельной работы

4. Нелинейное программирование

4.1.Задачи нелинейного программирования

4.2.Решение задачи нелинейного программирования методом множителей Лагранжа

Вопросы для самопроверки Задания для самостоятельной работы

Список литературы

3

Предисловие

Управление экономической системой реализуется как процесс, подчиняющийся опреде-

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

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

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

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

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

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

Математическое программирование включает методы нахождения экстремума (мини-

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

ограничениями.

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

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

определяющих диапазоны возможных изменений факторов.

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

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

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

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

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

де: найти переменные x1 , x2 ,...,xn , удовлетворяющие системе неравенств (уравнений).
i x1 , x2 ,...,xn bi , i 1,2,...,m	(1)
и обращающие в максимум (или минимум) целевую функцию, т.е.
z f x1 , x2 ,...,xn max min .	(2)

(Условия неотрицательности переменных, если они есть, входят в ограничения (1) ).

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

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

чение.

Как известно, упорядоченная совокупность значений n переменных x1 , x2 ,...,xn пред-

ставляется точкой n - мерного пространства. В дальнейшем такую точку будем обозначать

4

x

n

x

1

, x

2

,...,x

n

, а само оптимальное решение x

x , x

,...,x

.

n

1 2

n

В тех случаях, когда функции

f и i в задаче (1) – (2) хотя бы дважды дифференциру-

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

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

из-за многомерности функции определение ее максимального (или минимального) значения

(глобального экстремума) может оказаться весьма трудоемким – тем более, что этот экстре-

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

этих случаях для решения задачи (1) - (2) применяются методы математического программи-

рования.

Построение математической модели реального экономического процесса для форми-

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

ство, чем науку.

Если показатель эффективности z f x1 , x2 ,...,xn представляет линейную функ-

цию, а функции i x1 , x2 ,...,xn в системе ограничений (1) также линейны, то такая задача является задачей линейного программирования. Если исходя из содержательного смысла, ее решения должны быть целыми числами, то это задача целочисленного линейного програм-

мирования. Если в задаче математического программирования имеется переменная времени и критерий эффективности (2) выражается не в явном виде как функция переменных, а кос-

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

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

граммирования.

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

ваны:

1)по признаку моделируемых типов процессов,

2)по признаку свойств целевой функции и ограничений.

1) Классификация по признаку моделируемых типов процессов:

1.1) регулирование запасов,

1.2) распределение ресурсов,

1.3) организация обслуживания,

1.4) планирование замены оборудования,

5

1.5) другие, в т.ч. комбинированные процессы.

2) Классификация по признаку свойств используемых функций:

2.1) задача линейного программирования, когда целевая функция и ограничения задают-

ся линейными функциями; 2.2) задача целочисленного программирования, в которой есть ограничения на целочис-

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

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

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

ются нелинейными функциями.

В пособии нашли отражение основные из приведенных видов задач математического программирования.

Цель курса состоит:

1) в приобретении навыков построения типовых задач математического программиро-

вания,

2) в изучении методов решения типовых задач математического программирования.

В создание современного математического аппарата и развитие многих направлений ма-

тематического программирования большой вклад внесли российские ученые. Особо следует отметить роль академика Л.В.Канторовича, который в 1939 г., занявшись планированием ра-

боты агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудо-

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

ким видам транспорта и др. Л.В.Канторович сформулировал новый класс условно-

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

му направлению прикладной математики -линейному программированию.

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

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

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

сти в связи с этим шутливо-парадоксальное определение этих методов, сделанное одним из их создателей Т. Саати, как “искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами.”

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

6

1. Линейное программирование

1.1. Задача линейного программирования

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

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

1.1.1. Задача об ассортименте продукции

Словесная формулировка задачи

Фирма выпускает три вида изделий. В процессе производства используются три техно-

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

Операция 1

Операция 2

Операция 3

П

1 мин/изд.

3 мин/изд.

1 мин/изд.

Изделие 1

р

С

о

ы

д

р

у

2 мин/изд.

4 мин/изд.

ь

Изделие

2

к

е

ц

и

1 мин/изд.

2 мин/изд.

Изделие 3

я

Предельная

продолжи-

430 мин.

460 мин.

420 мин.

тельность

операций

Указана длительность технологических операций при изготовлении одного изделия каж-

дого вида, а также ограниченный в сутки фонд рабочего времени, в течение которого опера-

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

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

7

дов 1,2 и 3 составляет 3 , 2 и 5 у.е. соответственно.

Каков наиболее выгодный суточный объем производства каждого вида продукции?

Анализ словесной формулировки

Цель – максимизировать прибыль от продажи.

Ограничения – пределы времени использования операций.

Математическая формулировка задачи

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

x1 - количество изделий вида 1, x2 - количество изделий вида 2, x3 - количество изделий вида 3.

Тогда целевая функция будет выражать величину прибыли за сутки

z3x1 2 x2 5 x3 ,

аее максимизация обозначается

z3x1 2 x2 5 x3 max.

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

ничениями

для

операции

1 :

1x

1

2 x

2

1x

3

430

для

операции

2 :

3 x1

0 x

2

2 x3

460

,

для

операции

3 :

1x

1

4 x

2

0 x

3

420

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

x1 0 , x2 0 , x3 0 .

Математическая модель задачи z 3x1 2 x2 5 x3 max

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

1x	1	2 x	2	1x	3	430
3 x	1	0 x	2	2 x	3	460	,
1x	1	4 x	2	0 x	3	420
x1 0 , x2 0 ,					x3 0 .

8

1.1.2. Задача составления смеси (о диете)

Словесная формулировка задачи

Для испытания двигателей составляют смесь горючего объемом не менее 200 литров из

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

Вещества		А	Б	В	Стоимость одного литра
Компоненты					(в у.е.)
1		38%	-	-	0.04
2		0.1%	9%	2%	0.15
3		0.2%	50%	8%	0.4
Содержание	min	0.8%	22%	-
в смеси	max	1.2%	-	5%

Необходимо составить требуемую смесь минимальной стоимости.

Анализ словесной формулировки

Цель – минимизировать стоимость смеси.

Ограничения – объем смеси горючего и ее качество.

Математическая формулировка задачи

И стоимость, и объем, и качество смеси зависят от объема каждого из трех компонентов.

Поэтому в качестве искомых переменных выбираем: x1 - объем в литрах первого компонента в смеси, x 2 - объем в литрах второго компонента в смеси, x3 - объем в литрах третьего компонента в смеси.

Целевая функция будет представлять стоимость полученного объема смеси

z0.04 x1 0.15 x2 0.4 x3 ,

аее минимизация обозначается

z0.04 x1 0.15 x2 0.4 x3 min.

Необходимый объем смеси выражается ограничением x1 x2 x3 200 .

Качество смеси, зависящее от содержания в ней первого вещества, выражается ограни-

чениями

9

0.38 x1 0.001x2 0.002 x3 0.008 x1 x2 x3 , 0.38 x1 0.001x2 0.002 x3 0.012 x1 x2 x3 .

Качество смеси, зависящее от содержания в ней второго вещества, выражается ограни-

чением

0.09 x2 0.5 x3 0.22 x1 x2 x3 .

Качество смеси, зависящее от содержания в ней третьего вещества, выражается ограни-

чением

0.02 x2 0.08 x3 0.05 x1 x2 x3 .

Условие неотрицательности объемов компонентов выражается ограничениями x1 0 , x2 0 , x3 0 .

Математическая модель задачи

После приведения неравенств к стандартному виду окончательная математическая фор-

мулировка задачи представляется следующим образом: z 0.04 x1 0.15 x2 0.4 x3 min

при ограничениях
x1		x2		x3	200 ,
0.372 x1	0.007 x2		0.006 x3			0 ,
0.368 x1	0.011x2		0.01 0 x3			0 ,
0.220 x1	0.130 x2		0.280 x3			0 ,
0.050 x1	0.030 x2		0.030 x3			0 ,
x1 0 ,		x2 0 ,		x3 0 .

1.1.3. Задача о раскрое

Словесная формулировка задачи

Производятся исходные рулоны шириной 20 единиц. Поступил заказ, выполнение кото-

рого требует разрезания этих рулонов. Объем заказа, ширина заказываемых рулонов, воз-

можные варианты разрезания производимого рулона, количество получаемых при этом ру-

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

					10
Кол-во	Ширина		Возможные варианты разрезания рулонов
заказы-
	рулонов,			(количество получаемых рулонов)
ваемых
	ед.
рулонов
		1		2	3	4	5		6
150	5	0		2	2	4	1		0
200	7	1		1	0	0	2		0
300	9	1		0	1	0	0		2
Потери, ед.		4		3	1	0	1		2

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

6-ти вариантов, при которых удовлетворяются поступившие заказы с минимальными по-

терями.

Математическая модель

Идентификация переменных:

x j - количество исходных рулонов, разрезаемых по варианту j , j 1,2,...,6 ;

x7 , x8 и x9 - избыточное количество рулонов соответственно шириной 5, 7 и 9 единиц.

Избыточное количество рулонов шириной 5, 7 и 9 единиц, получаемое при разрезании исходных рулонов и превышающее заказанное количество, обозначим соответствующими переменными:

x	0 x	2 x	2 x	4 x	1x	0 x	150 ,
x78	1x11	1x22	0 x33	0 x44	2 x55	0 x66	200 ,
x9	1x1	0 x2	1x3	0 x4	2 x5	2 x6	300.

Целевая функция выражает суммарные потери:

z 4 x1 3x2 1x3 0 x4 1x5 2 x6 5 x7 7 x8 9 x9 .

В итоге, математическая модель имеет вид:

z 4 x1 3x2 1x3 0 x4 1x5 2 x6 5 x7								7 x8		9 x9 min
при ограничениях
0 x1 2 x2 2 x3 4 x4 1x5					0 x6	1x7	0 x8		0 x9	150,
1x1	1x2	0 x3	0 x4	2 x5	0 x6	0 x7	1x8		0 x9	200,
1x1	0 x2	1x3	0 x4	0 x5	2 x6	0 x7	0 x8		1x9	300,

x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 , x9 0.