Метод ветвей и границ целочисленное программирование статьи. Задача коммивояжера - метод ветвей и границ. Общий план решения задачи коммивояжера

Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 1 = х 1* , х 2 = х 2* , …, х k = х k * , при которых функция отклика (у ) достигает экстремального значения у = ext (оптимума).

Известны различные методы решения задачи оптимизации. Одним из наиболее широко применяемых является метод градиента, называемый также методом Бокса-Уилсона и методом крутого восхождения.

Рассмотрим сущность метода градиента на примере двухфакторной функции отклика y = f(x 1 , х 2 ). На рис. 4.3 в фак­торном пространстве изо­бражены кривые равных значений функции отклика (кривые уровня). Точке с координатами х 1 *, х 2 * соответствует экстремаль­ное значение функции от­клика у ext .

Если мы выбе­рем какую-либо точку фак­торного пространства в ка­честве исходной (х 1 0 , х 2 0), то наикратчайший путь к вершине функции откли­ка из этой точки – это путь, по кривой, касательная к которой в каждой точке совпадает с нормалью к кривой уровня, т.е. это путь в направлении гради­ента функции отклика.

Градиент непрерывной однозначной функции y = f (x 1 , х 2) – это вектор, определяемый по направлению градиентом с координатами:

где i, j – единичные векторы в направлении осей координат х 1 и х 2 . Частные производные и характеризуют направление вектора.

Поскольку нам неизвестен вид зависимости y = f (x 1 , х 2), мы не можем найти частные производные , и опреде­лить истинное направление градиента.

Согласно методу градиента в какой-то части факторного пространства выбирается исходная точка (исходные уровни) х 1 0 , х 2 0 . Относительно этих исходных уровней строится сим­метричный двухуровневый план эксперимента. Причем интер­вал варьирования выбирается настолько малым, чтобы ли­нейная модель оказалась адекватной. Известно, что любая кривая на достаточно малом участке может быть аппрокси­мирована линейной моделью.

После построения симметричного двухуровневого плана решается интерполяционная задача, т.е. строится линейная модель:

и проверяется ее адекватность.

Если для выбранного интервала варьирования линейная мо­дель оказалась адекватной, то может быть определено на­правление градиента:

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

где m – положительное число, определяющее величину шага в на­правлении градиента.

Поскольку х 1 0 = 0 и х 2 0 = 0, то .

Определив направление градиента () и выбрав ве­личину шага m , осуществляем опыт на исходном уровне х 1 0 , х 2 0 .

Затем делаем шаг в направлении градиента, т.е. осу­ществляем опыт в точке с координатами . Если значе­ние функции отклика возросло по сравнению с ее значением в исходном уровне, делаем еще шаг в направлении градиен­та, т.е. осуществляем опыт в точке с координатами:

Движение по градиенту продолжаем до тех пор, пока функция отклика не начнет уменьшаться. На рис. 4.3 движение по градиенту соответствует прямой, вы­ходящей из точки (х 1 0 , х 2 0). Она постепенно отклоняется от истинного направления градиента, показанного штриховой линией, вследствие нелинейности функции отклика.

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

Построив новую линейную модель , осуществляют регрессионный анализ. Если при этом провер­ка значимости факторов показывает, что хоть один коэф

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

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

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

1) исходные уровни факторов (х j 0) следует выбирать воз­можно ближе к точке оптимума, если есть какая-то априор­ная информация о ее положении;

2) интервалы варьирования (Δх j ) надо выбирать такими, чтобы линейная модель наверняка оказалась адекватной. Границей снизу Δх j при этом является минимальное значе­ние интервала варьирования, при котором функция отклика остается значимой;

3) значение шага (т ) при движении по градиенту выбирают таким образом, чтобы наибольшее из произведений не превышало разности верхнего и нижнего уровней факто­ров в нормированном виде

.

Следовательно, . При меньшем значении т разность функции отклика в исходном уровне и в точке с координа­тами может оказаться незначимой. При большем значении шага возникает опасность проскочить оптимум функ­ции отклика.

Метод градиентного спуска.

Направление наискорейшего спуска соответствует направлению наибольшего убывания функции. Известно, что направление наибольшего возрастания функции двух переменных u = f(x, у) характеризуется ее градиентом:

где e1, е2 - единичные векторы (орты) в направлении координатных осей. Следовательно, направление, противоположное градиентному, укажет направление наибольшего убывания функции. Методы, основанные на выборе пути оптимизации с помощью градиента, называются градиентными.

Идея метода градиентного спуска состоит в следующем. Выбираем некоторую начальную точку

вычисляем в ней градиент рассматриваемой функции. Делаем шаг в направлении, обратном градиентному:

Процесс продолжается до получения наименьшего значения целевой функции. Строго говоря, момент окончания поиска наступит тогда, когда движение из полученной точки с любым шагом приводит к возрастанию значения целевой функции. Если минимум функции достигается внутри рассматриваемой области, то в этой точке градиент равен нулю, что также может служить сигналом об окончании процесса оптимизации.

Метод градиентного спуска обладает тем же недостатком, что и метод покоординатного спуска: при наличии оврагов на поверхности сходимость метода очень медленная.

В описанном методе требуется вычислять на каждом шаге оптимизации градиент целевой функции f(х):

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

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

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

Метод наискорейшего спуска для случая функции двух переменных z = f(x,y).

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

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту -grad(/(x)), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным. Если нет дополнительной информации, то из начальной точки х (0 > лучше перейти в точку х (1) , лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска антиградиент -grad(/(x (^)) в точке х (к получим итерационный процесс вида

В координатной форме этот процесс записывается следующим образом:

В качестве критерия останова итерационного процесса можно использовать либо условие (10.2), либо выполнение условия малости градиента

Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий.

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

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

Более надежны и экономичны (в смысле количества итераций) градиентные методы с переменным шагом, когда в зависимости от полученного приближения величина шага некоторым образом меняется. В качестве примера такого метода рассмотрим метод наискорейшего спуска. В этом методе на каждой итерации величина шага я* выбирается из условия минимума функции /(х) в направлении спуска, т.е.

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции /(х) убывает. Поэтому на каждой итерации необходимо решать задачу одномерной минимизации по я функции ф(я) =/(х (/г) - - agrad^x^))). Алгоритм метода наискорейшего спуска состоит в следующем.

• 1. Зададим координаты начальной точки х^° точность приближенного решения г. Положим k = 0.
• 2. В точке х (/г) вычислим значение градиента grad(/(x (^)).
• 3. Определим величину шага а^ путем одномерной минимизации по я функции ср(я).
• 4. Определим новое приближение к точке минимума х (* +1 > по формуле (10.4).
• 5. Проверим условия останова итерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае полагаем k k + 1 и переходим к п. 2.

В методе наискорейшего спуска направление движения из точки х (*) касается линии уровня в точке х (* +1) . Траектория спуска зигзагообразная, и соседние звенья зигзага ортогональны друг другу. Действительно, шаг а^ выбирается путем минимизации по а функции (а ). Необходимое условие

минимума функции - = 0. Вычислив производную

сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

Задачу минимизации функции ф(я) можно свести к задаче вычисления корня функции одной переменной g(a) =

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

мало отличаются друг от друга, т.е. матрица Н(х) хорошо обусловлена. Однако на практике минимизируемые функции часто имеют плохо обусловленные матрицы вторых производных. Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее, чем в других направлениях. Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума, может вообще нарушить сходимость процесса градиентного спуска. Поэтому градиентные методы зачастую используются в комбинации с другими, более эффективными методами на начальной стадии решения задачи. В этом случае точка х (0) находится далеко от точки минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции.

Решение будем вести с использованием калькулятора . Возьмем в качестве произвольного маршрута:
X 0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
d i = min(j) d ij

i j	1	2	3	4	5	d i
1	M	90	80	40	100	40
2	60	M	40	50	70	40
3	50	30	M	60	20	20
4	10	70	20	M	50	10
5	20	40	50	20	M	20

Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i j	1	2	3	4	5
1	M	50	40	0	60
2	20	M	0	10	30
3	30	10	M	40	0
4	0	60	10	M	40
5	0	20	30	0	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij

i j	1	2	3	4	5
1	M	50	40	0	60
2	20	M	0	10	30
3	30	10	M	40	0
4	0	60	10	M	40
5	0	20	30	0	M
d j	0	10	0	0	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .

i j	1	2	3	4	5
1	M	40	40	0	60
2	20	M	0	10	30
3	30	0	M	40	0
4	0	50	10	M	40
5	0	10	30	0	M

Сумма констант приведения определяет нижнюю границу H:
H = ∑d i + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления

i j	1	2	3	4	5	d i
1	M	40	40	0(40)	60	40
2	20	M	0(20)	10	30	10
3	30	0(10)	M	40	0(30)	0
4	0(10)	50	10	M	40	10
5	0(0)	10	30	0(0)	M	0
d j	0	10	10	0	30	0

d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).

H(1*,4*) = 140 + 40 = 180
Исключение ребра (1,4) проводим путем замены элемента d 14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	40	40	M	60	40
2	20	M	0	10	30	0
3	30	0	M	40	0	0
4	0	50	10	M	40	0
5	0	10	30	0	M	0
d j	0	0	0	0	0	40

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d 41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

∑d i + ∑d j = 10

i j	1	2	3	5	d i
2	20	M	0	30	0
3	30	0	M	0	0
4	M	50	10	40	10
5	0	10	30	M	0
d j	0	0	0	0	10

Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 ≤ 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 150
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	5	d i
2	20	M	0(20)	30	20
3	30	0(10)	M	0(30)	0
4	M	40	0(30)	30	30
5	0(30)	10	30	M	10
d j	20	10	0	30	0

d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 150 + 30 = 180
Исключение ребра (3,5) проводим путем замены элемента d 35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.

i j	1	2	3	5	d i
2	20	M	0	30	0
3	30	0	M	M	0
4	M	40	0	30	0
5	0	10	30	M	0
d j	0	0	0	30	30

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d 53 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 10
После операции приведения сокращенная матрица будет иметь вид:

i j	1	2	3	d i
2	20	M	0	0
4	M	40	0	0
5	0	10	M	0
d j	0	10	0	10

Нижняя граница подмножества (3,5) равна:
H(3,5) = 150 + 10 = 160 ≤ 180
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 160
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	d i
2	20	M	0(20)	20
4	M	30	0(30)	30
5	0(20)	0(30)	M	0
d j	20	30	0	0

d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,2*) = 160 + 30 = 190
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	d i
2	20	M	0	0
4	M	30	0	0
5	0	M	M	0
d j	0	30	0	30

Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 20
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	d i
2	20	0	0
4	M	0	0
d j	20	0	20

Нижняя граница подмножества (5,2) равна:
H(5,2) = 160 + 20 = 180 ≤ 190
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 180
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,1) и (4,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,2), (2,1),
Длина маршрута равна F(Mk) = 180

Ниже приведено условие задачи и текстовая часть решения. Все решение полностью, в формате doc в архиве, вы можете скачать. Некоторые символы могут не отображаться на странице, но документе word все отображается. Еще примеры работ по ЭМММ можно посмотреть

ПОСТАНОВКА ЗАДАЧИ

Издательское предприятие должно выполнить в течении недели (число дней m = 5) работу по набору текста с помощью работников n категорий (высокая, средняя, ниже средней, низкая). Требуются определить оптимальную численность работников по категориям, при которой обеспечивается выполнение работы с минимальным расходом фонда зарплаты при заданных ограничениях. Исходные данные приведены в таблице 1 и 2.

Таблица 1

Таблица 2

Задача должна решаться методом целочисленного линейного программирования в Mathcad 2000/2001.

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ ЗАДАЧИ

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

Решение задачи целочисленного программирования выполняется в два этапа.

На первом этапе выполняется задача линейного программирования без учета целочисленности.

На втором этапе производится пошаговый процесс замены нецелочисленных переменных ближайшими верхними или нижними целыми значениями.

Сначала решается, задача без учета условия целочисленности.

Целевая функция определяется по формуле:

где Q - общий фонд зарплаты на выполнение работы;

x 1 , x 2 , …, x n - численность работников по категориям;

n - число категорий работников;

c 1 , c 2 ,…, c n - дневная тарифная ставка одного работника по категориям;

m - число рабочих дней в неделю, m = 5.

Целевую функцию можно записать в векторной форме:

При решении задачи должны выполняться следующие ограничения. Ограничение сверху

x ≤ d (1)

задает максимальную численность работников по категориям, где d —вектор, определяющий численность по категориям.

В ограничении

учтено, что общая численность работников не должна превышать k max .

В ограничении снизу

р × х≥Р (3)

отражается, что все работники вместе должны выполнить заданный объем работ Р .

В качестве последнего ограничения записывается условие неотрицательности вектора переменных

x ≥0 (4)

Математическая модель решения задачи без учета условия целочисленности включает следующие выражения:

x ≤ d

р × х≥Р ,

x ≥ 0 .

Модель целочисленного программирования должна включать выражения (5), а также дополнительные ограничения, с помощью которых нецелочисленные переменные х заменяются целочисленными значениями. Конкретные выражения модели с целочисленными переменными рассмотрены в следующем подразделе.

РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD

Исходные данные для примера даны в табл. 1 и 2.

Для решения задачи используется пакет Mathcad с функцией Minimize. Данная функция определяет вектор решения задачи:

х := Minimize (Q , x ),

где Q — выражение целевой функции, определяющей минимальный фонд зарплаты, х - вектор переменных.

Сначала задача решается без учета условия целочисленности. Это решение приведено в Приложении 1. В первой строке введены нулевые начальные значения вектора х и целевая функция Q (x ) . После слова Given и перед функцией Minimize указаны ограничения. В результате получена нецелочисленная оптимальная численность по категориям:

х =

с фондом зарплаты Q = 135 у. е.

Из данного решения находится целочисленное решение методом ветвей и границ.

Сначала в полученном решении анализируется дробная величина х 4 =
= 1,143. Для нее можно задать два целочисленных значения: х 4 = 1 и х 4 = 2. Начинается построение дерева решений (Приложение 2). На дереве решений откладывается начальный нулевой узел. Затем он соединяется первым узлом х 4 , и из этого узла проводятся две ветви, соответствующие ограничениям: х 4 = 1 и х 4 = 2.

Для ветви с ограничением х 4 = 1 решается задача линейного программирования, данная в Приложении 1, с учетом этого ограничения.

В результате получено решение этой задачи. Переменная х 1 стала целочисленная, но переменная х 2 стала дробной х 2 = 0,9.

Для продолжения ветви создается узел х 3 и ветвь х 3 = 1. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1. С этими ограничениями задача имеет решение х Т =
= (1,938 1 1 1).

Для продолжения ветви создается узел х 1 и ветвь х 1 = 2. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1, х 1 = 2. С этими ограничениями задача имеет решение х Т = = (2 1 1 1).

Процесс построения дерева решении и выполнение задачи линейного программирования повторяется, пока не будут построены все ветви.

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

Из результативных выбирается наилучшее и оно принимается как оптимальное целочисленное решение всей задачи с минимальной величиной Q (x ) . В нашем случае мы имеем два оптимальных целочисленных решения

Q (х) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

Следовательно, издательская организация должна привлечь для набора текста двух работников высокой категории, одного работника средней категории, одного работника ниже средней категории и одного работника низкой категории. Возможен так же другой равнозначный вариант привлечения работников: один работник высокой категории, один работник средней категории, два работника категории ниже средней и два работника низкой категории. В обоих вариантах затраты будут минимальными и составят 140 ден. ед.

Скачать решение задачи:

Имя файла: 2.rar
Размер файла: 24.99 Kb

Если закачивание файла не начнется через 10 сек, кликните