Файл: 1ЭМММ-Линейное программирование.pdf

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

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

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

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

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

Набережные Челны: Изд-во КамПИ, 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