Обзор основных направлений линейного и математического программирования
Математическое программирование очень обширная область современной математики и её обстоятельное изложение потребовало бы несколько томов книг. Поэтому укажем лишь основные направления, по которым велись и ведутся математические исследования.
Развитие симплекс-метода
Целочисленное линейное программирование
В целом ряде решаемых задач линейного программирования на переменные 
накладывается дополнительное условие их целочисленности. Простое округление до целых чисел здесь не помогает план может получиться не оптимальным. Поэтому приходится разрабатывать специальные алгоритмы решения таких задач.
Булевское программирование
К частному случаю задачи целочисленного линейного программирования относятся задачи, где переменные могут принимать всего лишь два значения 0 и 1. Соответствующие задачи часто называют задачами булевского программирования. Наиболее известные из этих задач это задача о назначениях (какого работника на какую работу поставить), задача выбора маршрута (задача коммивояжера, задача почтальона), задача о максимальном паросочетании и т.д.
Для решения задач этого типа разрабатываются очень специфические алгоритмы, основанные на комбинаторике, графах и т.д.
Стохастическое линейное программирование
Бывает много практических ситуаций, когда сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения.
|
|
|
Квадратичное программирование
Выпуклое программирование
Геометрическое программирование
Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области.
Дискретное программирование
Динамическое программирование
Теория массового обслуживания
Теория игр
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Задачи математического и линейного программирования
Математическое программирование – это раздел высшей математики, посвящённый решению задач, связанных с нахождением экстремумов функций нескольких переменных при наличии ограничений на переменные.
Построение математической модели включает следующие этапы: 1) выбор переменных задачи; 2) составление системы ограничений; 3) выбор целевой функции.
Переменными задачи называются величины 
, которые полностью характеризуют процесс. Их обычно записывают в виде вектора 
.
|
|
|
Системой ограничений задачи называется совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из условий, например, условия положительности переменных. В общем случае они имеют вид
Целевой функцией называют функцию 
переменных задачи, которая характеризует качество выполнения задачи, и экстремум которой требуется найти.
Общая задача математического программирования формулируется следующим образом: найти переменные задачи , которые обеспечивают экстремум целевой функции
(1)
и удовлетворяют системе ограничений
(2)
Если целевая функция (1) и система ограничений (2) линейны, то задача математического программирования называется задачей линейного программирования.
Допустимым решением (планом) задачи линейного программирования называется любой n–мерный вектор , удовлетворяющий системе ограничений и условиям неотрицательности. Множество допустимых решений образует область допустимых решений.
Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.
Дата добавления: 2022-12-03; просмотров: 40; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!