1ЭМММ-Линейное программирование

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

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

ориентированы на использование современных информационных технологий.

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

Составители: Смирнов Ю.Н., Шибанова Е.В.

Набережные Челны: Изд-во КамПИ, 2004, 81 с.

Рецензент: доцент, кандидат физико-математических наук Углов А.Н.

Печатается по решению научно-методического

совета Камского государственного политехнического института от 24.03.03 г.

Камский Государственный Политехнический Институт, 2004

2

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

2.Общая, стандартная и основная задачи линейного

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

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

5.Симплекс - метод решения задач линейного

3

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Введение

Линейное программирование является одним из разделов математического программирования – дисциплины,

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

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

gi (x1, x2,..., xn ) <>= bi ,i =1, m , где f и gi - заданные функции, а bi

- заданные постоянные величины. При этом ограничения в виде равенств определяют множество допустимых решений, а x1, x2,..., xn - называются проектными параметрами.

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

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

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

линейного программирования (ЛП), когда все функции f и gi -

линейные.

Нелинейное программирование – если хотя бы одна из функций f и gi - нелинейная.

Выпуклое программирование – если отыскивается минимум выпуклой (максимум вогнутой) функции, заданной на выпуклом замкнутом множестве.

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

Дробно-линейное программирование – если целевая функция f – квадратичная, gi - линейные.

Параметрическое программирование – если функции f и gi зависят от некоторых параметров.

Стохастическое программирование – если в функциях f

и gi содержаться случайные величины.

4

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Динамическое программирование – если процесс нахождения решения является многоэтапным.

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

Линейное

программирование

Линейное

целочисленное

программирование

Целочисленное

программирование

Параметрическое

программирование

Дробно-линейное

программирование

Рис.1. Схема задач математического программирования

1. Примеры задач линейного программирования

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

Для производства n видов продукции предприятие использует m видов ресурсов (сырья). Известны нормы затрат ресурсов для производства единицы продукции каждого вида: aij - норма затрат i – ого ресурса для производства единицы

продукции j – ого вида.

5

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Ресурсы предприятия имеются в ограниченных объемах b1,b2 ,...,bm . Предположим, прибыль (доход) от реализации

единицы продукции каждого вида величина известная, равная c j .

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

Обозначим через x j ( j =1, n) план производства каждого

вида продукции.

Экономико-математическая модель данной задачи:

Найти максимальное значение линейной функции цели

n

(прибыли или дохода) z = å c j × x j ® max

j=1

при линейных ограничениях

n

å aij × x j £ bi , i = 1, m (ограничения на ресурсы);

j=1

x j ³ 0, j = 1, n (условие неотрицательности плана производства).

Ниже будет показано, что эта задача нахождения

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

Замечания:

1. Величины c j должны быть определены на основе

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

2. В модели не учтены емкость рынка и объем поступивших заказов. Учет этих факторов рынка можно

записать в виде ограничений d j ≤ x j ≤ Dj , где d j , Dj соответственно объем заказов и предельная емкость рынка j -

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

3. Оптимальный объем и номенклатура производства

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

6

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

ресурсов bi 0 , но и объемом выделенных финансов на производство Q . Тогда ограничения на ресурсы и финансы

запишутся в виде следующих неравенств

n

åaij × x j £ bi 0 + bi ,i = 1, m

j=1

m

å yi × bi £ Q

i=1

где yi - цены на ресурсы, определяемые также из маркетинговых исследований, bi - искомые объемы закупаемых

ресурсов.

Таким образом, процесс математического

моделирования реальных задач сводится к все большему учету реальных факторов. Эти факторы оказываются связывающими различные деловые процессы предприятия. В нашем случае оказались связанными задачи таких деловых процессов, как, ПРОИЗВОДСТВО, МАРКЕТИНГ, МАТЕРИАЛЬНО- ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ, СБЫТ, ФИНАНСЫ.

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

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

Предположим, банк имеет свободных средств в размере 120 млн. рублей. Выданные кредиты или обязательства банка по кредитам составляют не менее 30 млн. рублей. Исходя из стратегии (безопасности) банка, не менее чем 40% всех используемых средств должны находиться в ценных бумагах (в ликвидных ресурсах, для выполнения возможных непрогнозируемых обязательств). Определить оптимальный

7

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

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

Экономико-математическая модель задачи:

Предположим, x1, x2 средства банка размещенные

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

Найти максимум линейной целевой функции – функции дохода

Z = 0,2 × x1 + 0,1× x2 ® max

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

объему выдаваемых кредитов и по стратегии банка

ìx1 + x2 £ 120 ïïx1 ³ 30

íïx2 ³ 0,4(x1 + x2 )

ïîx1, x2 ³ 0

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

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

О п р е д е л ен и е 1 . Общей задачей ЛП называется задача нахождения максимального (минимального) значения

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

n

z = å c j x j ® min(max) (1) при условиях

j=1

8

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

где aij , bi , c j - заданные постоянные величины и k £ m .

О п р е д е л ен и е . 2 . Функция Z называется целевой функцией задачи (1 - 4), x j - проектными параметрами задачи,

а условия (2 - 4) ограничениями данной задачи.

ограничения заданы только в виде неравенств (2), и все

проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде равенств отсутствуют:

(минимального) значения функции (1) при выполнении условий (3), (4), где k=0, l=n, m<n, т.е. когда ограничения заданы только в виде равенств (3), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде неравенств

(2) отсутствуют:

9

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Все три формы задачи ЛП эквивалентны, ибо каждая из

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

1. Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков

2. Ограничения-неравенства (2) можно заменить эквивалентными ограничениями-равенствами путем введения

дополнительных неотрицательных переменных следующим образом:

n

Ограничение-неравенство вида å aij x j £ bi j =1

При этом число дополнительных переменных равно числу преобразуемых неравенств.

10

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com