Содержание
7
2 Теоретическая часть 8
2.1 Обзор численных методов решения задач ЛП 8
2.2 Алгоритм симплекс-метода для задачи на минимум 8
2.3 Двойственный симплекс-метод 10
3Расчетная часть 12
ВВЕДЕНИЕ
Оптимизация – целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Поиски оптимальных решений привели к созданию специальных математических методов и уже в XVIII веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины XX века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев – невозможно.
Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:
количество продукции – расход сырья,
количество продукции – качество продукции,
время работы – прибыль от проделанной работы.
Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.
На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации.
Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.
В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач.
Теория принятия решений – область исследования, вовлекающая понятия и методы математики, статистики, экономики, менеджмента и психологии; изучает закономерности выбора путей решения разного рода задач, а также исследует способы поиска наиболее выгодных из возможных оптимальных решений.
Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Можно сказать, что оно применимо для построения математических моделей технологических процессов, в основу которых может быть положена гипотеза линейного представления реального мира: задач управления запасами, задач планирования и управления, задач распределения ресурсов, оптимального размещения оборудования и др.
Задачи линейного программирования - задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств.
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения.
1 Построение математической модели
Составление модели начинаем с выбора
переменных, совокупность числовых
значений которых однозначно определяет
один из вариантов процесса. Для каждой
i-й задачи вj-м узле и для каждогоj-го узла введем переменную
,
которая может принимать всего два
значения (0 или 1):
Тогда искомая модель может быть представлена матрицей вида:
Ограничения задачи:
(1.1)
(1.2)
(1.3)
(1.4)
Таким образом, математическая модель задачи о распределении является задачей целочисленного квадратичного программирования вида:
(1.5)
где pi– допустимое время решенияi-й задачи.
при ограничениях (1.1), (1.3) , (1.4) и
(1.6)
и вида:
(1.7)
где
–
допустимые затраты вj-м узле.
при ограничениях (1.2) , (1.3) , (1.4), (1.6).
(1.1)-ограничение по времени ;
(1.2)-ограничение по стоимости;
(1.3)-один узел либо выполняет одну задачу, либо нет ;
(1.4)-одна задача выполняется только одним узлом ;
Полученная задача является задачей целочисленного программирования.