Контрольная работа на тему Контрольная работа 140413-05

Содержание


Тема 1. Линейное и целочисленное программирование. 2
Тема 2. Динамическое программирование. 9
Тема 3. Математическая теория оптимального управления. 12
Тема 4. Теория игр. 14
Тема 5. Теория графов, сетевое планирование и системы массового обслуживания. 16
Тема 6. Элементы теории управления рисками. 19
Список используемой литература 22

Тема 1. Линейное и целочисленное программирование.

Теоретические вопросы.

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

Двойственная задача.
Ответ:
Если задана общая задача ЛП:

где D определяется системой уравнений и неравенств:


то двойственной по отношению к ней называется общая задача ЛП:


где D* определяется системой уравнений и неравенств



Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:
1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.
2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.
3. Матрица ограничений задачи А транспонируется.
4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, хj?0 или ui?0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (аjи?сj или aix?bi).
5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, aix?bi или аjи?сj), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (ui?0 или хj?0).
Из приведенного определения вытекает важное свойство – симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей:
((D*)*, (f*)*)?(D, f),

Графический метод решения задач линейного программирования.
Ответ:
Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные.
Найти минимальное (максимальное) значение функции:


при ограничениях вида


и