- •1. Понятие модели.
- •1.1. Модели и моделирование. Классификация моделей
- •В настоящее время для постижения истины существует 3 пути:
- •1.2. Классификация моделей
- •1.3. Адекватность моделей
- •2. Математические модели и методы их расчета
- •2.1. Математические модели.
- •2.1. Понятие операционного исследования
- •2.3. Этапы построения математических моделей
- •Можно выделить следующие основные этапы построения математической модели:
- •2.4 Математические оптимизационные модели.
- •2.4. Необходимые сведения из матричной алгебры
- •2.5. Системы линейных алгебраических уравнений
- •2.5. Модель Леонтьева многоотраслевой экономики (балансовый анализ).
- •3. Простейшие оптимизационные задачи.
- •3.1. Экстремумы функции одной переменной.
- •Экстремумы функции нескольких переменных.
- •4. Математические модели экономических задач.
- •4.1. Транспортная задача
- •4.2 Задача об использовании ресурсов.
- •4.3. Задача о диете.
- •4.4. Общая формулировка задачи линейного программирования
- •Стандартная задача линейного программирования.
- •Каноническая задача линейного программирования.
- •Общая задача линейного программирования.
- •5. Графический метод решения задач линейного программирования.
- •5.1. Выпуклые множества
- •5.2 Геометрический смысл решений систем неравенств.
- •5.3. Графический метод решения задач линейного программирования. Пример.
- •5.4. Геометрический метод решения задачи. Общий случай.
- •6.Симплекс-метод решения задачи линейного программирования.
- •6.1. Выпуклые многогранники.
- •6.2.Симплекс-метод. Пример.
- •6.3.Симплекс метод. Общий случай.
- •Симплекс-таблицы. Пример.
- •7.Двойственность в линейном программировании.
- •7.1. Двойственные задачи линейного программирования.
- •7.2. Теоремы двойственности..
- •7.3. Анализ чувствительности задачи линейного программирования..
- •Решение транспортной задачи.
- •7.1 Особенности транспортной задачи.
- •7.2. Опорный план транспортной задачи
- •7.3. Метод потенциалов.
- •8.Задачи нелинейного программирования.
- •8.1. Общая постановка задачи нелинейного программирования.
- •8.2. Задачи нелинейного программирования с линейной целевой функцией и нелинейными ограничениями.
- •8.3. Задачи нелинейного программирования с нелинейной целевой функцией и линейными ограничениями.
- •8.4. Метод множителей Лагранжа.
- •Элементы теории игр.
- •9.1.Основные понятия теории игр
- •8.3. Сведение матричной игры к задаче линейного программирования.
6.3.Симплекс метод. Общий случай.
Общая задача линейного программирования решается тем же способом, как и рассмотренный нами пример.
Найдем наибольшее значение функции
=c1x1+c2x2+ ... +cnxn (1)
при ограничениях
а11x1+а12x2+ ... +а1nxn = b1
а21x1+а22x2+ ... +а2nxn = b2 (2)
... ... ... ... ... ... ... ...
аm1x1+аm2x2+ ... +аmnxn = bm
х1 0, х2 0 ... хn 0 (3)
Если система (2) не имеет решения, то и вся задача линейного программирования не имеет решения. Если система (2) имеет единственное решение, то оно и будет решением задачи линейного программирования (других просто не может быть). Поэтому для нас представляет интерес случай, когда система (2) имеет не единственное решение ( в алгебре показывается, что в этом случае решений будет бесчисленное множество). В этом случае часть переменных будет свободными переменными, а остальные – базисными. Базисные переменные выражаем через свободные. Пусть х1 , х2 ,... хs – базисные переменные, а – свободными переменными.
Представим (2) в виде
причем будем считать, что ( в противном случае изменим свободные переменные как это делали в предыдущем примере).
Подставляя в(1) вместо базисных переменных их выражения из (4) запишем целевую функцию через свободные переменные
f( )= (5)
Возможны три случая.
А. Все числа , , …, неположительны. Тогда ( решение задачи линейного программирования. Действительно, в этом случае max f=f(0,…,0)= , так как при увеличении значение функции f может только уменьшиться.
Б. Среди чисел есть положительные (пусть, например числа (коэффициенты при в (4) )неотрицательны. Тогда задача линейного программирования не имеет решения.
Действительно, положим в этом случае
.
Тогда (4) примет вид
и при любом будем иметь . Поэтому можно сделать сколь угодно большим положительным числом, но в этом случае f = при неограниченном возрастании , а это значит что наибольшего значения функция f не имеет.
В. Среди чисел есть положительные (пусть, например, ), но среди чисел имеются отрицательные.
В этом случае мы поступаем следующим образом (в дальнейшем будем говорить делаем шаг).
Находим такое отрицательное число для которого величина наименьшая. Далее переводим в свободную переменную, а в базисную переменную, для чего в (4) выражаем переменные через переменные и через эти переменные выражаем функцию f.
Отсюда следует алгоритм решения задачи линейного программирования симплекс-методом.
Приводим систему ограничений к допустимому виду (4), а целевую функцию к к виду (5).
Если среди чисел нет положительных, то задача решена (случай А).
Если среди чисел есть положительные (пусть, например числа (коэффициенты при в (4) )неотрицательны. Тогда задача линейного программирования не имеет решения. (случай Б)
Если среди чисел есть положительные (пусть, например, ), но среди чисел имеются отрицательные, то мы делаем шаг.
Для этого находим такое отрицательное число для которого величина наименьшая. Далее переводим в свободную переменную, а в базисную переменную. После этого переходим к пункту 2.
Замечание. Если рассматривается задача нахождения наименьшего значения целевой функции (5) при ограничениях (4), то алгоритм решения задачи линейного программирования симплекс-методом будет следующим..
Приводим систему ограничений к допустимому виду (4), а целевую функцию к к виду (5).
Если среди чисел нет отрицательных, то задача решена
Если среди чисел есть отрицательные (пусть, например числа (коэффициенты при в (4) )неотрицательны. Тогда задача линейного программирования не имеет решения.
Если среди чисел есть отрицательные (пусть, например, ), но среди чисел имеются отрицательные, то мы делаем шаг.
Для этого находим такое отрицательное число для которого величина наименьшая. Далее переводим в свободную переменную, а в базисную переменную. После этого переходим к пункту 2.