Реферат: Кафедра «Прикладная математика» Экономические приложения линейного программирования

Кафедра «Прикладная математика»


Экономические приложения линейного программирования

(аннотация курса по выбору)


Авторы программы: доц. В.М. Гончаренко, д. ф.-м. н. В.Ю. Попов


Задачи, которые обсуждаются при чтении данной дисциплины по выбору, в полном смысле являются ответом на вопрос: зачем экономисты изучают на первом курсе математику, в частности, линейную алгебру. Ясно, что большая часть идей и методов, которые рассматриваются во второй части курса линейной алгебры, связаны с решением основной проблемы экономики – проблемы оптимизации – математическими методами. Дисциплина «Экономические приложения линейного программирования» дает качественную иллюстрацию того, как изученные методы применяются при решении экономических задач. В частности, в спецкурсе рассматриваются дополнительные вопросы линейного программирования, связанные с экономическими задачами.

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

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

• задача об оптимальном назначении, т.е. оптимальном выборе кандидатов на предложенные вакансии;

• задача о заключении контрактов;

• задача об оптимизации перевозки неоднородных грузов;

• транспортная задача по критерию времени, т.е. оптимизируется не стоимость всех перевозок, а время, на эти перевозки затраченное.

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

• задача о коммивояжере (задача о выборе кратчайшего маршрута в сети дорог между городами и возвращением в исходный пункт);

• задача о «рюкзаке» (задача о заполнении ограниченного по массе объема с наибольшей эффективностью) и т.д.

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

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

Постановка транспортной задачи. Задачи с правильным и неправильным балансом. Открытая и закрытая модели.

Методы нахождения оптимального решения транспортной задачи. Распределительный метод, метод потенциалов, метод дифференциальных рент. Задачи с неправильным балансом. Блокировка.

Распределительные задачи. Перевозка неоднородных грузов. Задача об оптимальном назначении. Общая распределительная задача.

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

Двойственный симплекс-метод. Метод сечений Гомори и его геометрическая интерпретация.

Задачи параметрического программирования и их экономические приложения.