Симплекс-метод

Н.Е. Гучек

Доцент, кандидат технических наук

КОНСПЕКТ ЛЕКЦИЙ

по дисциплине

Методы оптимальных решений

Часть 2

Направление подготовки: 080100 «Экономика»

Профили подготовки: «Финансы и кредит», «Бухгалтерский учет, анализ и

аудит», «Менеджмент»

Форма обучения: заочная

Тула 2013 г.

Конспект лекций подготовлен доцентом Н.Е. Гучек и обсужден на заседании кафедры «Финансы и менеджмент» факультета ЭиМ,

протокол № 1 от 31 августа 2012 г.

Зав. кафедрой __________________________Е.А. Федорова

Конспект лекций пересмотрен и утвержден на заседании кафедры «Финансы и менеджмент» факультета экономики и менеджмента,

протокол № 1 от 30 августа 2013 г.

Зав. кафедрой __________________________Е.А. Федорова

Конспект лекций пересмотрен и утвержден на заседании кафедры «Финансы и менеджмент» института права и управления,

протокол № 1 от 29 августа 2014 г.

Зав. кафедрой __________________________Е.А. Федорова

Содержание

Лекция 1. Симплексный метод решения задачи линейного программирования………………………………………………………………………...4

1.1. Простой симплекс-метод (метод А) ……………………………………............4

1.2.Симплексные таблицы и алгоритм решения задач………………………………5

1.3. Применение симплексного метода в экономических задачах…………………7.

Лекция 2. Двойственные задачи линейного программирования……………………………11

2.1. Двойственный симплекс-метод. 11

2.2. Экономическая интерпретация объективно обусловленных оценок и исследование задачи распределения ресурсов …………………………………………………………………………20

Лекция 3. Транспортная задача…………………………………………………………………………27

3.1.Экономико-математическая модель транспортной задачи. 27

3.2. Нахождение первоначального базисного распределения поставок. 31

Лекция 4. Особые случаи транспортной задачи. 36

4.1. Вырожденность в транспортных задачах. 36

4.2. Открытая транспортная задача. 39

Библиографический список………………………………………………………………...44

Лекция 1. Симплексный метод решения задачи линейного программирования

План.

1.1. Простой симплекс-метод (метод А)

1.2.Симплексные таблицы и алгоритм решения задач.

1.3. Применение симплексного метода в экономических задачах.

Симплекс-метод

Симплексный метод является универсальным, так как позволяет решать практически любую задачу линейного программирования, заданную в каноническом виде. Идея симплекс метода была разработана русским ученым Л.В. Канторовичем в 1939 г. На основе этой идеи американский ученый Д. Данцинг в 1949 г. разработал симплекс-метод, позволяющий решать любую задачу линейного программирования.

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

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

Симплексный метод состоит из трех основных элементов:

1) определения какого-либо первоначального допустимого базисного решения задачи;

2) правила перехода к лучшему решению;

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

Симплекс-метод состоит из двух вычислительных процедур:

- симплекс-метод с естественным базисом;

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

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

Для применения симплекс-метода с естественным базисом ЗЛП в каноническом виде должна содержать единичную подматрицу порядка m, в этом случае очевиден первоначальный опорный план (неотрицательное базисное решение системы ограничений).

Симплексный метод с искусственным базисом применяется при отсутствии первоначального опорного плана исходной ЗЛП в каноническом виде. Такая ситуация возникает при наличии в исходном ограничении знаков «равно» либо «больше или равно».