Задача линейного программирования

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

(1) при условиях (2) (3)

 

(4) где - заданные постоянные величины и . Функция (1) называется целевой функцией (или линейной формой) задачи (1) – (3), а условия (2) – (4) – ограничениями данной задачи. Задача линейного программирования будет иметь канонический вид, если в основной задаче вме сто первой системы неравенств имеет место система уравнений. Основную задачу можно свести к канонической путём введения дополнительных переменных.

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

Классификация оптимизационных задач: 1 классс-задачи распределения: транспортные задачи, задачи о назначениях, задачи о раскрое, задачи о смесях, задачи распределения; 2 класс – задачи управления запасами; 3 класс – задачи теории массового обслуживания:4 класс-задачи выбора маршрута; 5 – задачи теорий расписаний; 6 – задачи теории игр; 7 – задачи ремонта;8 – задачи поиска и 9 – аналитические задачи.

В общем случае задача линейного программирования может быть записана в таком виде:

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X1, X2,...,Xn) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3). Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности. Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР). Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.

 

Поиск кратчайших путей

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

1. алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами); Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от некоторой вершины s к рассматриваемой вершине. Эти пометки постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации только одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от t к рассматриваемой вершине.

2. алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин); В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе. Алгоритм:1)Перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D0, каждый элемент di,j которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ∞. Кроме того, положить значения диагонального элемента di,iравным 0. 2)Для целого m, последовательно принимающего значения 1...N определить по элементам матрицы Dm-1 элементы Dm 3) Алгоритм заканчивается получением матрицы всех кратчайших путей DN, N – число вершин графа.

3. алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами). Делается это так: Будем вести список кандидатов в кратчайшие пути. Hаходится первый кратчайший путь. Так как все другие пути не должны совпадать с первым путем, то эти остальные пути не содержат как минимум одно из ребер первого пути. Поэтому, выкидываем по одному ребру из первого пути и находим кратчайшие пути в получаемых графах. Hайденные пути (с пометкой о том, какое ребро было выкинуто) добавляем в список кандидатов. Из списка кандидатов выбираем самый короткий путь - это второй самый короткий путь. Далее находим следующий самый короткий путь аналогично. При нахождении каждого самого короткого пути в список кандидатов добавляется не более N новых путей (на самом деле конечно меньше). При удалении ребра нахождение кратчайшего пути в полученном графе производится за линейное время. Для этого в исходном графе алгоритм Дейкстры запускается как от начальной, так и от конечной вершины. При удалении одного ребра кратчайший путь в новом графе ищется с использованием деревьев, полученных для исходного графа.