Федосеев В.В. и др. Экономико-математические методы и прикладные модели

Подождите немного. Документ загружается.

Основы,

линейного программирования

Слова «наилучшим образом» здесь означают выбор неко-

торого критерия оптимальности, т.е. некоторого экономиче-

ского показателя, позволяющего сравнивать эффективность

тех или иных планово-управленческих решений. Традици-

онные критерии оптимальности: «максимум прибыли», «ми-

нимум затрат», «максимум рентабельности» и др.

Слова «учитывало бы внутренние возможности и внеш-

ние условия производственной деятельности» означают, что

на выбор планово-управленческого решения (поведения) на-

кладывается ряд условий, т.е. выбор X осуществляется из

некоторой области возможных (допустимых) решений D;

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

Таким образом, реализовать на практике принцип опти-

мальности в планировании и управлении — это значит ре-

шить экстремальную задачу вида:

max(min)/(x), (2.1)

XeD, (2.2)

где м^Ч — математическая запись критерия оптималь-

ности — целевая функция. Задачу условной оптимизации

(2.1),

(2.2) обычно записывают в виде:

Найти максимум или минимум функции

,-л

f{Xj= f(x

, ..-,*„)

при ограничениях (pi(*i, х

, ...,

){<,

=,>}Ь

Фг(*1 ,х

,...,х

)

{<,

(2.4)

<?m(xi>

, -., х

){<,=,>}Ь

Xj>0J=l,n. (2.5)

Условие (2.5) необязательно, но его всегда при необходи-

мости можно добиться. Обозначение [<,=,>} говорит о том,

что в конкретном ограничении возможен один из знаков:

<,= или >. Более компактная запись:

Глава 2

max(min)/Y*i,

,...,

), (2.6)

<Pi(*i>*2> ...,х

){<,=,>}b

i=l, m, (2.7)

х; > 0,/=lTra. (2.8)

Задача (2.6)-(2.8) — общая задача оптимального (мате-

матического) программирования, иначе — математическая

модель задачи оптимального программирования, в основе

построения (разработки) которой лежат принципы опти-

мальности и системности.

Вектор X (набор управляющих переменных Xj, j

п )

называется допустимым решением, или планом задачи оп-

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

ме ограничений. А тот план X (допустимое решение), кото-

рый доставляет максимум или минимум целевой функции

f(xi, *2, ..., х

), называется оптимальным планом (оптималь-

ным поведением, или просто решением) задачи оптимально-

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

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

ведения в конкретной производственной ситуации связан с

проведением с позиций системности и оптимальности эко-

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

оптимального программирования.

Задачи оптимального программирования в наиболее об-

щем виде классифицируют по следующим признакам.

По характеру взаимосвязи между

переменными —

а) линейные,

б) нелинейные.

В случае а) все функциональные связи в системе ограни-

чений и функция цели — линейные функции; наличие не-

линейности хотя бы в одном из упомянутых элементов при-

водит к случаю б).

По характеру изменения перемен-

ных —

а) непрерывные,

б) дискретные.

Основы линейного программирования

В случае а) значения каждой из управляющих перемен-

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

тельных чисел; в случае б) все или хотя бы одна переменная

могут принимать только целочисленные значения.

По учету фактора времени —

а) статические,

б) динамические.

В задачах а) моделирование и принятие решений осуще-

ствляются в предположении о независимости от времени

элементов модели в течение периода времени, на который

принимается планово-управленческое решение. В случае б)

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

не может быть и необходимо учитывать фактор времени.

По наличию информации о перемен-

ных —

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

нированные),

б) задачи в условиях неполной информации,

в) задачи в условиях неопределенности.

В задачах б) отдельные элементы являются вероятност-

ными величинами, однако известны или дополнительными

статистическими исследованиями могут быть установлены

их законы распределения. В случае в) можно сделать пред-

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

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

П о числу критериев оценки альтер-

натив —

а) простые, однокритериальные задачи,

б) сложные, многокритериальные задачи.

В задачах а) экономически приемлемо использование од-

ного критерия оптимальности или удается специальными

процедурами (например, «взвешиванием приоритетов») све-

сти многокритериальный поиск к однокритериальному; при-

меры многокритериальных задач рассмотрены в гл. 3.

Сочетание признаков 1—5 позволяет группировать (клас-

сифицировать) в самом общем виде задачи и методы опти-

мального программирования, например: 1а)2а)3а)4а)5а) —

задачи и методы линейного программирования, 1б)2а)3а)

4а)5а) — задачи и методы нелинейного программирования,

Глава 2

1а)2б)3а)4а)5а) — задачи и методы целочисленного (дис-

кретного) линейного программирования и т.д.

Рассмотрим пример задачи оптимального программиро-

вания.

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

тов Pi, P2, ..., Pj, ..., Р

, тщательная экономическая проработ-

ка которых позволяет получить для каждого из проектов Pj

достаточно убедительные экономические оценки ожидаемого

эффекта от его реализации Cj и необходимой величины

капиталовложений gj. Общий объем возможных инвести-

ций ограничен величиной G. Необходимо так распорядить-

ся имеющимися финансовыми ресурсами, чтобы максимизи-

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

Математическая запись задачи (модель). Введем в рас-

смотрение управляющие переменные, пусть:

_ J1, если проект Pj следует инвестировать,

' [0, если не следует.

С учетом этих обозначений задача по критерию «макси-

мум экономического эффекта» математически запишется

следующим образом:

max f(Xi,x

, ...,x

) =Y^

i '

7=1

Xj e

|0;l};

j = 1, п. ^J

Приведенная задача является задачей дискретного линей-

ного программирования с булевыми переменными (перемен-

ные,

которые могут принимать только два значения: 1 и О,

т.е.

«да» или «нет»), т.е. относится к классу задач

1а)2б)3а)4а)5а). Эта задача может быть решена, например,

известным методом Балаша.

Выбору метода решения конкретной задачи оптимально-

го программирования предшествует ее классификация, т.е.

отнесение к одному из классов оптимизационных задач, на-

чиная с приведенных самых общих признаков (например,

Основы линейного программирования

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

переменными).

Развитие и совершенствование методов решения задач

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

случаям типа б), в).

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

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

метод последовательного улучшения плана (симплекс-ме-

тод),

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

(реализуется) этим методом. Именно эти задачи в дальнейшем

рассматриваются в данной главе.

2.2.

Формы записи задачи линейного программирования

и ее экономическая интерпретация

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

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

дач,

для которых разработаны эффективные методы реше-

ния. Наиболее изученным подклассом задач являются зада-

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

В задаче линейного программирования (ЗЛП) требуется

найти экстремум (максимум или минимум) линейной целе-

вой функции fix):

max(min) fix) = C\Xi + c

+ ••• + C„JC„ (2.9)

при ограничениях (условиях):

ll*l + °12*2 + •••+ ^„x^

{<,=,>}

&i,

21*l + <*22*2 + -..+ а

2п

{<,=,>}Ъ

, (2.10)

«mi*i + a

+ ...+ a

{<,=,>}b

Xj>0;j=T^i, (2.11)

где aq,bi,Cj(i=l,m;j—l,n) — заданные постоянные величины.

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

вания в развернутой форме; знак {<,=,>} означает, что в кон-

Глава 2

кретной ЗЛП возможно ограничение типа равенства или

неравенства (в ту или иную сторону).

Систему ограничений (2.10) называют функциональны-

ми ограничениями ЗЛП, а ограничения (2.11) — прямыми.

Вектор X = (*i, X2, ..., х

), удовлетворяющий системе ог-

раничений (2.10), (2.11), называется допустимым решением,

или планом ЗЛП, т.е. ограничения (2.10), (2.11) определяют

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

ного программирования (область определения ЗЛП).

План (допустимое решение), который доставляет максимум

или минимум целевой функции (2.9), называется опти-

мальным планом (оптимальным решением) ЗЛП.

Канонической формой записи задачи линейного програм-

мирования (КЗЛП) называют задачу вида (запись с исполь-

зованием знаков суммирования):

Найти max f(x\ = У^

CjXj

при ограничениях V a^Xj =

т,

Xj > 0, b

> 0, i =1, т,; j

=1,

п . (2.14)

Векторная форма записи КЗЛП имеет вид:

Найти max f{x) = СХ

при ограничениях А\Х\ +

+ ... +

= В, х > 0,

где С = (с

, ..., с

), X = (х

, ..., х

СХ — скалярное произведение векторов С,Х\

А;

и. В — вектор-столбцы:

4i]

,А

, ... , А

—

'О

mnJ

,B =

)

Матричная форма записи КЗЛП:

(2.12)

(2.13)

Основы линейного программирования

тах/(х)=СХ

при условиях АХ =

В,

Здесь С

(ci,

сз,...,

) — вектор-строка; А

) — матри-

ца размерности тохп, столбцами которой являются вектор-

столбцы

А]-;

— вектор-столбец,

— вектор-столбец.

Иногда используется стандартная форма записи ЗЛП:

max(min)

f(x)

= СХ,

АХ < (>)5,

При этом запись

X > 0

понимают как вектор (или век-

тор-столбец

зависимости от контекста),

которого все ком-

поненты (элементы) неотрицательны.

Приведение ЗЛП

каноническому виду осуществляется

введением

левую часть соответствующего ограничения вида

(2.10)

k-й

дополнительной переменной

п+

со знаком

в случае ограничения типа >

знаком

+ в

случае ограниче-

ния типа

Если

на

некоторую переменную

не

накладывается ус-

ловие неотрицательности,

то

делают замену переменных

= х'

х", х'

я" >

0. В

преобразованной задаче

все

переменные неотрицательные. Переход

задаче

на

макси-

мум достигается изменением

случае необходимости знака

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

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

ния приводят исследования конкретных производственно-

хозяйственных ситуаций, которые

том или ином виде ин-

терпретируются

как

задачи

об

оптимальном использова-

нии ограниченных ресурсов (задача

раскрое, смесях, дие-

те

т.д.).

Глава 2

•ь.

Пример 1 (задача о смесях). Стандартом предусмотрено,

что октановое число автомобильного бензина А-76 должно

быть не ниже 76, а содержание серы в нем — не более

0,3%.

Для изготовления такого бензина на заводе использу-

ется смесь из четырех компонентов. Данные о ресурсах сме-

шиваемых компонентов, их себестоимости и их октановом

числе, а также о содержании серы приведены в таблице

Характеристика

Компонент автомобильного бензина

№ 1

№ 2 №3

№4

Октановое число 68

Содержание серы, % 0,35

Ресурсы, т 700

Себестоимость, ден.ед./т 40_

0,35

600

0,3

500

0,2

300

Требуется определить, сколько тонн каждого компонента

следует использовать для получения 1000 т автомобильного

бензина А-76, чтобы его себестоимость была минимальной.

Решение. Для решения этой задачи сформулируем

ее экономико-математическую модель, т.е. сформулируем

задачу математически. Введем необходимые обозначения:

пусть Xj (j =

1,2,3,4)

— количество в смеси компонента с

номером ;. С учетом этих обозначений имеем задачу (кри-

терий оптимальности — «минимум себестоимости»):

min /(ЗГ) = 40*! + 45х

60*

90*

+ Х

+ *

+ *4 = Ю00» (1)

68*!

+ 72*2 + 80*3 + 90х

^ 76

•

1000,

0,35xi + 0,35*2 +

0,3*3

0,2*4

^ 0,3-1000,

*х < 700,

< 600,

< 500,

< 300,

> 0, / = 1,2,3,4.

(2)

(3)

Основы линейного программирования

Функциональное ограничение (1) отражает необходи-

мость получения заданного количества смеси (1 000 т), (2) и

(3) — ограничения по октановому числу и содержанию серы

в смеси, остальные — ограничения на имеющиеся объемы

соответствующих ресурсов (компонентов). Прямые ограни-

чения очевидны, но принципиально важны для выбора ме-

тода решения.

Полученная математическая задача — задача линейного

программирования. Она может быть решена симплекс-мето-

дом, который рассмотрен в данной главе ниже. В результа-

те решения получается оптимальное решение

X = (*!, х

, х

)

= 571 т,

х\=

0, х

= 143 т, х\ = 286 т.

Подставляя найденное решение в целевую функцию,

имеем

f(x*) = 40- 571 + 45-0 + 60-143 + 90-286 =57 160,0 (ден. ед.).

Таким образом, оптимальному решению X будет отве- *

чать минимальная себестоимость в 57160,0 ден. ед. -^

и*» Пример 2 (использование ограниченных ресурсов).

На участок строящейся дороги необходимо вывезти

20 000 м

каменных материалов. В районе строительства

имеются три карьера с запасами 8 000 м

, 9 000 м

и 10 000 м

Для погрузки материалов используются экскаваторы, имеющие

производительность 250 м

в смену в карьерах 1 и 2 и 500 м

в смену в карьере 3.

Эти карьеры обеспечивают каменными материалами так-

же ряд других строящихся объектов. На погрузку материа-

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

ров общий лимит 60 машино-смен с правом использования

его по усмотрению строителей.

Транспортные затраты на перевозку материалов характе-

ризуются показателями: для перевозки 10 000 м

материа-

лов из карьера 1 требуется 1 000 автомобиле-смен, из карь-

Глава 2

ера 2 — 1 350, из карьера 3 — 1 700 автомобиле-смен. Тре-

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

щий минимальные транспортные затраты.

Решение. Сформулируем экономико-математическую

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

материалов 10 000 м

Обозначим через Xi объем добычи материалов в карьере

#2 — в карьере 2, *з — в карьере 3. Необходимо миними-

зировать транспортные затраты:

min f(x) = 1 OOOxj + 1 350*2 + 1 700х

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

х%

+ х$

—

2,0, (1)

40*!

+ 40х

+ 20лг

< 60, (2)

0 < х

0,8, (3)

0 < х

0,9, (4)

0<х

<1,0. (5)

Условие (1) отражает потребность в материалах, (2) — ог-

раничение по наличию ресурса «фонд рабочего времени экс-

каваторов» (мы не можем использовать больше того, что у

нас в наличии). Условия (3)-(5) отражают тот факт, что до-

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

материалов в соответствующих карьерах. Полученная зада-

ча — задача ЛП; решив ее симплекс-методом (см. ниже),

найдем оптимальный план (решение)

Х^= (xl,x*

,xl) :**= 0,8 (8 000м

);

0,2 (2 000м

); *J= 1,0 (10 000 м

Таким образом, из карьера 1 следует вывезти 8 000 м

материалов, из карьера 2 — 2 000 м

, из карьера 3 — 10 000 м

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

транспортными затратами

f(X*) = 1 000

•

0,8 + 1 350

•

0,2 + 1 700 • 1,0 = 2 770 j

(автомобиле-смен).

2.3.

Математический аппарат

Изучение и понимание современных экономико-матема-

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