Доп. Вопросы Формулировка задачи математического программирования (мп)
При решении нашей задачи можно выделить nпеременных, которые можем варьировать.
Целевая функция f(xN) – нелинейна для всех или части переменных.
Имеется также gi(xN)>=0,i=1,q
Как формулируется задача.
Должно быть задано:
Max(илиmin) целевой функцииf(xN)
g(xN) >=0
h(xN) =0
На физическом уровне: Нужен резервуар в виде открытого сверху параллелепипеда из листа металла. Нужно обеспечить макс объем при фиксированной площади стенок. Лист металла S= А.
В транспортных, экономических и т.п. задачах – этих переменных может быть десятки и даже сотни. И есть методы, которые эти задачи решают.
Если все входящие функции f,gиh– линейные функции, то имеем задачу линейного программирования.
Когда формулируют задачу линейного программирования, то, обычно, знак переменных выделяют отдельной строкой.
Объединяют в матрицу:
Оптимальное решение – одно. Поэтому словосочетание «Наиболее оптимальное» или «Самое оптимальное» - это полная безграмотность.
Классификация задач мп
Задачи нелинейного программирования
Целочисленное линейное программирование.
Если имеем линейную задачу, в которой переменные принимают целочисленные линейные значения то имеем целочисленное линейное программирование
Смешанное целочисленное программирование
Комбинация линейный и нелинейных переменных
Стохастическое программирование
Бывают задачи когда отдельные переменные либо коэффициенты являются с.в. то они описываются
Задача линейного программирования
Линейное программирование - это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.
С формально-математической точки зрения задача линейного программирования может быть описана следующим образом:
найти неизвестные величины
оставляющие
при условии выполнения системы неравенств
или в векторно матричной нотации:
Суть симплекс-метода
Задача линейного программирования.
Целевая функция
Ограничения:
Подобные задачи сводятся к матричному виду и решаются с помощью метода «Симплекс-метод». Он предложен американским исследователем Данцлетом в 60е годы 20го века и является наиболее эффективным методом решения подобных задач.
Существует несколько модификаций симплекс-метода.
Основная идея– берется плоскость (пространство), а далее в силу ограничений выявляется, что область допустимых решений будет представлять собой область (выпуклый многоугольник) в первом квадрате.
В основе – ряд теорем, что решение единственное и находится на угловых точках. Симплекс-метод преобразует неравенства к матрице. С помощью стандартных методов находят угловые точки, затем в какой-то из точек вычисляют целевую функцию. Выбирается определенная последовательность движения от точки к точке. Число точек конечно, но их может быть достаточно много.