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

Слайд #1

Математическое моделирование

Слайд #2

Основы моделирования. Детерминированные задачи

Понятие решения. Множество решений, оптимальное решение. Показатель эффективности решения
Математические модели, принципы их построения, виды моделей.
Задачи: классификация, методы решения, граничные условия.
Общий вид и основная задача линейного программирования. Симплекс – метод.
Транспортная задача. Методы нахождения начального решения транспортной задачи. Метод потенциалов.
Общий вид задач нелинейного программирования. Графический метод решения задач нелинейного программирования. Метод множителей Лагранжа.
Основные понятия динамического программирования: шаговое управление, управление операцией в целом, оптимальное управление, выигрыш на данном шаге, выигрыш за всю операцию, аддитивный критерий, мультипликативный критерий.
Простейшие задачи, решаемые методом динамического программирования.
Методы хранения графов в памяти ЭВМ. Задача о нахождении кратчайших путей в графе и методы ее решения. Задача о максимальном потоке и алгоритм Форда–Фалкерсона.

Слайд #3

1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
В настоящее время в литературе насчитывается несколько десятков
определений понятая "модель", отличающихся друг от друга. Под моделью
будем понимать условный образ какого-либо объекта, приближенно
воссоздающий этот объект с помощью некоторого языка. В экономико-
математических моделях таким объектом является экономический процесс
(например, использование ресурсов, распределение изделий между
различными типами оборудования и т.п.), а языком - классические и
специально разработанные математические методы.

Слайд #4

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

Слайд #5

Можно выделить три основных этапа проведения экономико-
математического моделирования. На первом этапе ставятся цели и задачи
исследования, проводится качественное описание объекта в виде
экономической модели. На втором этапе формируется математическая модель
изучаемого объекта, осуществляется выбор (или разработка) методов
исследования, проводится программирование модели на ЭВМ,
подготавливается исходная информация.

Слайд #6

Далее проверяются пригодность машинной модели на основании правильности получаемых с ее помощью результатов и оценка их устойчивости. На третьем, основном, этапе экономико-математического моделирования осуществляются анализ математической модели, реализованной в виде программ для ЭВМ, проведение машинных расчетов, обработка и анализ полученных результатов.

Слайд #7

Процедура экономико-математического моделирования заменяет
дорогостоящие и трудоемкие натуральные эксперименты расчетами.
Действительно, при использовании экономико-математических методов
достаточно быстро и дешево производится на ЭВМ сравнение
многочисленных вариантов планов и управленческих решений.

Слайд #8

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

Слайд #9

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

Слайд #10

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

Слайд #11

Общей задачей линейного программирования называют задачу:
при ограничениях:
хj– произвольные где – заданные действительные числа.

Слайд #12

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
Целевая функция:
При ограничениях:
неотрицательное условие – векторная форма записи задачи линейного программирования.
Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
целевая функция

Слайд #13

при ограничениях:
– матричная форма записи задачи линейного программирования.
Введем обозначения: C = ( c1, c2, …, cn)
где С – матрица-строка; А – матрица системы уравнений, Х – матрица-столбец переменных, В – матрица-столбец свободных членов.
Тогда матричная форма записи задачи линейного программирования примет вид:

Слайд #14

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
целевая функция
при ограничениях:
, – стандартная форма записи задачи линейного программирования.

Слайд #15

Каноническая форма записи задачи линейного программирования имеет вид:
Симметричной формой записи задачи линейного программирования называют задачу:
при ограничениях:
или задачу

Слайд #16

при ограничениях:
Любую задачу линейного программирования можно свести к задаче
линейного программирования в канонической форме. Для этого в общем
случае нужно уметь сводить задачу максимизации к задаче минимизации;
переходить от ограничений неравенств к ограничениям равенств и заменять
переменные, которые не подчиняются условию не отрицательности.
Максимизация некоторой функции эквивалентна минимизации той же
функции, взятой с противоположным знаком, и наоборот.

Слайд #17

Все формы задачи линейного программирования эквивалентны, так как
каждая из них с помощью некоторых преобразований может быть переписана
в форме другой задачи. При этом необходимо пользоваться следующими
правилами:
1. Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков коэффициентов на противоположные, поскольку
2. Ограничения-неравенства можно заменить эквивалентными ограничениями-равенствами путем введения дополнительных неотрицательных переменных следующим образом:
Неравенство вида , преобразуется в равенство
Неравенство
в равенство

Слайд #18

При этом число дополнительных переменных равно числу преобразуемых неравенств. Вводимые дополнительные переменные имеют вполне определенный
смысл. Например, для задачи распределения ресурсов числовое значение дополнительной переменной равно объему неиспользованного соответствующего ресурса. С математической точки зрения основные и дополнительные переменные играют одинаковую роль, поэтому целесообразно их единое обозначение.
1. Каждое ограничение-равенство можно записать в виде двух неравенств

Слайд #19

2. Переменную неограниченную условием не отрицательности, можно заменить разностью двух дополнительных неотрицательных переменных: