Динамическое программирование (стр. 8 из 10)

1.4.2 Алгоритм двойственного симплекс-метода

Существует двойственный симплекс-метод, или метод последовательного уточнения оценок. Отличие двойственного симплекс-метода от прямого в том, что:

А) двойственный симплекс-метод работает с недопустимым опорным планом;

Б) признаком оптимальности решения является отсутствие в столбце значений базисных переменных отрицательных элементов;

В) выбор разрешающей строки и разрешающего столбца производятся по правилам:

Пересчет элементов таблицы производится так же, как в прямом симплекс-методе.

Примечание 1. При решении задач, использующих в качестве элемента алгоритма дробную часть числа существенно увеличивается влияние ошибок округления вплоть до возможного получения неправильного решения. Поэтому дробную часть следует брать от числа с обыкновенной дробью. Это условие значительно усложняет программную реализация 1-го алгоритма Гомори.

Примечание 2. Алгоритм Гомори работает со следующей формой ЗЛП, т.е. задача на максимум и ограничения на равенствах.

1.4.3 Геометрическая интерпретация первого алгоритма Гомори

Для того, чтобы дать геометрическую интерпретацию алгоритма Гомори по шагам нужно произвести переход от представления отсечений через дополнительные переменных канонической системы и переменные отсечений к их представлению через основные переменные.

Это позволяет представить допустимую область k -го шага как объединение области предыдущего шага и осчечения ^l_k:

1,2,... .

Ограничение ^l_k получается из правой части выражения для переменной отсечения, вводимой в базис на шаге k , если выразить входящие в выражения переменные через основные переменные исходной задачи. В результате применения алгоритма Гомори мы переходим от невыпуклой области к выпуклой, причем, искомое решение, являющееся вершиной выпуклой области на предпоследнем шаге лежит на грани и на последнем шаге станет вершиной. Т.е. в общем случае, ограничения-отсечения соединяют точки невыпуклой области, делая ее выпуклой.

Примечание. Алгоритм отсечения работает только с равенствами и требует целочисленности для всех переменных, поэтому система, в которую вошли дополнительные переменные, должна быть совместна. Когда выбираем переменную, по которой будем строить отсечение желательно, чтобы в базис вводилась переменная из множества переменных основных и дополнительных, а не «бывшая» переменная отсечения.

Двойственный симплекс метод по-другому называется l -методом. Если в результате решения l -задачи получается множество оптимальных планов, то метод отсечения применять нельзя.

1.5 ПРИБЛИЖЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗЦП

К приближенным методам относят метод ближайшего соседа, метод Фогеля, метод приближенного решения задачи о контейнерных перевозках.

1.5.1 Метод ближайшего соседа

Применяется для решения задачи о коммивояжере. Последовательно строятся n путей, в каждом из которых началом берутся i1,2,... n , а переход осуществляется по кратчайшему расстоянию между пунктами.

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

Алгоритм ближайшего соседа употребляется для:

1) поиска приближенного решения, которое может быть использовано для приближенного решения задачи;

2) поиска приближенного решения, которое используется в качестве первого рекорда в алгоритме Литтла.

1.5.2 Задача о контейнерных перевозках

Постановка:

a_j-вес единицы продукции, j 1, n; ^c_j-ценность единицы продукции, j 1, n;

b - допустимый вес (объем, протяженность) контейнера;

^x_j - количество продукции, j 1, n.

max

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

1. Предположение:

- включать в контейнер продукцию с большим ^c_j;

- включать в контейнер продукцию с малым ^a_j.

Схема метода:

- вводится прямоугольная система координат XOY( AOC) ;

на плоскости строятся точки с координатами ^a_j,^c_j, строится луч

, совпадающий с осью OC при k0 ;

этот луч начинают вращать по часовой стрелке, момент перехода луча через l -тую точку ^a_l,^c_l фиксируется как шаг алгоритма kl ;

- на каждом шаге алгоритма производится назначение ^x_l единицей и вычисляется текущее значение левой части ограничения на вместимость контейнера; если ограничение не выполняется, то последнее назначение отменяется и осуществляется переход к следующей точке.

Процесс продолжается до тех пор, пока лучом не будет пройдена последняя точка из множества j N

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

1.5.3 Метод Фогеля для решения задачи о назначении

^c_ij - показатель эффекта от назначения кандидата на место j ;

Данную задачу будем решать на максимум суммарного эффекта. Ее можно решить приближенно за n шагов так, что на каждом шаге конкретная работа закрепляется за одним кандидатом. Метод является эвристическим. Его положения:

1) выбор работы j для исполнителя i или исполнителя i для работы j из набора возможных N , должно производиться по наибольшему значению показателя эффекта ^c_ij;

2) назначение i на j или j на i должно производиться так, чтобы любое другое назначение заметно ухудшало значение функции полезности.

Схема алгоритма:

на каждом шаге k1,2,... n для каждого исполнителя i из N и работы j из N определяется разность между двумя наибольшими элементами

;

из полученных _i^k, ^k_j выбирается наибольшее, тем самым определяется направление назначе-

k ния: если элемент в строке, т.е. _i наибольший, то исполнитель назначается на работу, если элемент в столбце, то работа закрепляется за исполнителем;

А) если максимальный элемент обнаружен в строке i * , то для исполнителя i * выбирается работа с наибольшей полезностью, т.е. j * выбирается так, что ^c_i* j* max , производится назначение i * на j * , т.е. ^x_i* j* 1 , i*, j* вычеркиваются;

Б) если максимальный элемент обнаружен в столбце j * , то ищется исполнитель с наибольшим значением эффекта, т.е. i * выбирается так, что ^c_i* j* max , производится закрепление j * за кандидатом на i * , т.е. ^x_i* j* 1 , i*, j* вычеркиваются;

4) 1-3 повторяются до тех пор, пока не останется 1 элемент, соответствующий последнему назначению.

I	J	1	2	…	N
1
2
…
N

1.6 ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ С БУЛЕВЫМИ ПЕРЕМЕННЫМИ. АДДИТИВНЫЙ МЕТОД БАЛАША

Рассмотрим задачу с булевыми (бивалентными) переменными:

(2) .

(3)

Пробным планом задачи (4)-(7) называется любой ( nm) -мерный вектор U X, Y , удовлетворяющий

(5)-(6).

Пробный план называется планом, если он удовлетворяет (7) и псевдопланом, если он не удовлетворяет

(7).

План называется оптимальным, если он удовлетворяет (4).