Модели линейного программирования злп
доктор технических наук, профессор И.Г. Кантаржи
(Московский государственный строительный университет)
кандидат физико-математических наук, доцент В.И. Самарин
(Сочинский государственный университет туризма и курортного дела)
Печатается по решению Ученого совета факультета информационных технологий и математики Сочинского государственного университета туризма и курортного дела от 5 июля 2007 г. протокол №10.
А13 Математическое программирование: Курс лекций: Учебное пособие для студентов 2-го курса экономических специальностей / Под ред. И.Л. Макаровой. – Сочи: СГУТиКД, 2007. – 123 с.: табл.
Пособие содержит определения, правила, алгоритмы, теоремы и формулы, необходимые для решения задач по математическому программированию. Излагаются методы решения задач линейного программирования, транспортной задачи, элементы теории двойственности, матричных игр, рассматриваются дискретное, нелинейное, динамическое программирование, программирование на сетях. Приводится достаточное количество задач экономического содержания с решениями.
Для студентов экономических специальностей высших учебных заведений.
Тема 1. Математическая модель задачи линейного
Тема 2. Графический метод решения ЗЛП. Закономерности и общие
Тема 3. Симплексный метод решения ЗЛП………………………………………23
Тема 4. Модифицированный симплекс-метод решения ЗЛП. Устойчивость
Тема 5. Двойственность в линейном программировании……………………….42
Тема 6. Элементы теории матричных игр………………………………………. 49
Тема 7. Матричные статистические игры………………………………………. 58
Тема 8. Транспортная задача………………………………………………………64
Тема 9. Дискретное программирование…………………………………………..77
Тема 10. Элементы нелинейного программирования……………………………84
Тема 11. Метод динамического программирования……………………………..91
Тема 12. Программирование на сетях…………………………………………. 101
Тема 13. Планирование на сетях…………………………………………………115
Учебное пособие представляет собой курс лекций по разделу математики «Математическое программирование» для экономических специальностей (080109 «Бухгалтерский учет, анализ и аудит», 080504 «Государственное и муниципальное управление», 080507 «Менеджмент организации», 080102 «Мировая экономика», 080105 «Финансы и кредит», 080502 «Экономика и управление на предприятии») в объеме одного семестра в соответствии с Государственным образовательным стандартом высшего профессионального образования (2000 г.).
Данное учебное пособие представляет собой теоретический материал практической направленности по разделу курса математики «Математическое программирование» для экономических специальностей и является необходимой составной частью достижения цели проводимого исследования по теме «Формирование специальных профессиональных умений студентов-экономистов на занятиях по математическим дисциплинам», ведущей идеей которого является содержательное методическое изменение деятельности преподавателя и студентов-экономистов на занятиях по математическим (непрофильным) дисциплинам с целью формирования и совершенствования профессиональных знаний и умений будущих специалистов в области экономики.
Экономические проблемы, возникающие перед специалистами, в своем большинстве, зависят от множества различных, иногда противоречащих друг другу факторов, изменяются с течением времени и влияют на другие проблемы и процессы. Вследствие этого исследование экономической проблемы целесообразно проводить на адекватной математической модели. Математическая модель отражает проблему в абстрактной форме и позволяет учесть большое число разнообразных характеристик, от которых зависит эта проблема. Анализ и расчет математической модели позволяют выбрать оптимальные решения поставленной задачи и обосновать этот выбор.
Данное учебное пособие посвящено изложению построения математических моделей, методов расчета и их применению для решения экономических задач. На многочисленных примерах подробно и доступно объяснены математические методы расчета представленных моделей.
В каждой теме в популярной форме даны общая постановка задачи, построение для нее математической модели и методы ее расчета. Представлены экономические проблемы, оптимальное решение которых становится возможным после использования соответствующей математической модели. Это задачи о наилучшем использовании ресурсов, транспортная задача, задачи нахождения оптимальной стратегии, оптимального планирования инвестиций и целый ряд других.
В темах 1-5 рассмотрены модели линейного программирования – постановка и примеры типовых задач, теоретические основы, теория двойственности, симплексный и графический методы решения задач. Темы 6, 7 посвящены рассмотрению решения задач теории парных матричных игр и матричных статистических игр, тема 8 – решению транспортных задач различными методами. В теме 9 представлены методы целочисленного линейного программирования. В теме 10 описываются классические методы оптимизации задач нелинейного программирования. Тема 11 рассматривает модели задач динамического программирования, используемые при решении таких актуальных задач, как задача об оптимальном распределении средств между предприятиями, задача о замене оборудования. Темы 12 и 13 включают в себя элементы теории графов, сетевого планирования и управления.
В конце каждой темы представлен список профессиональных умений студентов-экономистов, формирование которых возможно и целесообразно на данном занятии.
Для усвоения студентами материала пособия не требуется специальных знаний по математике кроме тех, которые входят в программу подготовки студентов экономического профиля, а именно: линейная алгебра, аналитическая геометрия на плоскости, математический анализ, теория вероятностей и математическая статистика.
Поскольку выпускники вузов по экономическим специальностям в последующей практической деятельности будут встречаться с математическими методами оптимизации, главным образом, как пользователи, а не разработчики, в данном пособии основное внимание уделяется приложениям математических методов в экономике, а не их подробному теоретическому обоснованию. По этой причине в пособии приводится достаточное количество содержательных примеров, иллюстрирующих приемы математического моделирования экономических ситуаций с последующим экономическим анализом полученных результатов.
Лекция 3. Линейное программирование
3.1. Линейное программирование как инструмент математического моделирования экономики
Линейное программирование сформировалось как отдельный раздел прикладной математики в 40 – 50-х гг. ХХ в. благодаря работам советского ученого, лауреата Нобелевской премии Л.В. Канторовича. В 1939 году им была опубликована работа «Математические методы организации и планирования производства», в которой он с использованием математики решил экономические задачи о наилучшей загрузке машин, раскрое материалов с наименьшими расходами, распределении грузов по нескольким видам транспорта и другие, предложив метод разрешающих множителей 8 .
Л.В. Канторович впервые сформулировал такие широко используемые экономико-математические понятия, как оптимальный план, оптимальное распределение ресурсов, объективно обусловленные оценки, указав многочисленные области экономики, где они могут быть применены.
Понятие линейного программирования было введено американским математиком Д. Данцигом, который в 1949 г. предложил алгоритм решения задачи линейного программирования, получивший название «симплексный метод».
Математическое программирование, в которое входит линейное программирование, в настоящее время является одним из направлений исследования операций. В зависимости от вида решаемых задач в нем выделяют такие области, как линейное, нелинейное, дискретное, динамическое программирование и др. Термин «программирование» введен в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определяют программу или план работы некоторого экономического объекта.
В классическом математическом анализе исследуются общая постановка задачи определения условного экстремума. Однако в связи с развитием промышленного производства, транспорта, агропромышленного комплекса, банковского сектора традиционных результатов математического анализа оказалось недостаточно. Потребности практики и развитие вычислительной техники привели к необходимости определения оптимальных решений при анализе сложных экономических систем.
Главным инструментом для решения таких задач является математическое моделирование. При этом сначала строится простая модель, затем проводится ее исследование, позволяющее понять, какие из интегрирующих свойств объекта не улавливаются формальной схемой, после чего за счет усложнения модели обеспечивается большая ее адекватность реальности. Во многих случаях первым приближением к действительности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, являются линейными. Практика показывает, что достаточное количество экономических процессов достаточно полно описывается линейными моделями. Следовательно, линейное программирование как аппарат, позволяющий отыскивать условный экстремум на множестве, заданном линейными уравнениями и неравенствами, играет важную роль при анализе этих процессов.
Линейное программирование получило широкое развитие в связи с тем, что было установлено: ряд задач сферы планирования и управления может быть сформулирован в виде задач линейного программирования, для решения которых имеются эффективные методы. По оценкам специалистов примерно 80–85 % всех решаемых на практике задач оптимизации относится к задачам линейного программирования.
Созданный математический аппарат в сочетании с компьютерными программами, производящими трудоемкие расчеты, позволяет широко использовать модели линейного программирования в экономической науке и практике.
Определение 1 9 .Линейное программирование (ЛП) – это область математического программирования, являющегося разделом математики и изучающего методы поиска экстремальных (наибольших и наименьших) значений линейной функции конечного числа переменных, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые представляют количественные соотношения между переменными, выражающие условия и требования экономической задачи и математически записываются в виде уравнений или неравенств, называются системой ограничений.
К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения.
Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции, называемой целевой 10 :
(3.1)
от n переменных x1, x2, …, хn при наложенных функциональных ограничениях:
(3.2)
и прямых ограничениях (требовании неотрицательности переменных)
, (3.3)
где aij, bi, cj – заданные постоянные величины.
В системе ограничений (3.2) знаки «меньше или равно», «равно», «больше или равно» могут встречаться одновременно.
ЗЛП в более краткой записи имеет вид:
,
;
.
Вектор Х = (x1, x2, …, хn) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называют планом (или допустимым решением) ЗЛП.
Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции f(X), называется оптимальным планом задачи и обозначается f(X * ), где Х * =(x1 * , x2 * , …, хn * ).
Еще одна форма записи ЗЛП:
,
где f(X * ) есть максимальное (минимальное) значение f(С, х), взятое по всем решениям, входящим в множество возможных решений Х.
Определение 2 11 . Математическое выражение целевой функции и ее ограничений называются математической моделью экономической задачи.
Для составления математической модели необходимо:
2) составить целевую функцию исходя из цели задачи;
3) записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности.