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

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

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

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

1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

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

В результате отбираются наиболее оптимальные варианты.

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

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

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

Математическая модель задачи ЛП (линейного программирования):

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

при ограничениях:

хj– произвольные где – заданные действительные числа.

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

Целевая функция:

При ограничениях:

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

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

целевая функция

при ограничениях:

– матричная форма записи задачи линейного программирования.

Введем обозначения: C = ( c 1 , c 2 , …, c n )

где С – матрица-строка; А – матрица системы уравнений, Х – матрица-столбец переменных, В – матрица-столбец свободных членов.

Тогда матричная форма записи задачи линейного программирования примет вид:

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

целевая функция

при ограничениях:

, – стандартная форма записи задачи линейного программирования.

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

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

или задачу

при ограничениях:

при ограничениях:

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

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

1. Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков коэффициентов на противоположные, поскольку

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

Неравенство вида , преобразуется в равенство

Неравенство

в равенство

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

1. Каждое ограничение-равенство можно записать в виде двух неравенств

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