Задача о назначениях и венгерский метод ее решения.




ЗНАЕТЕ ЛИ ВЫ?

Задача о назначениях и венгерский метод ее решения.



Для решения задачи о назначениях составляют таблицу (табл. 3.6.1):

Таблица 3.6.1

В левой колонке записаны номера кандидатов, в верхней строке – номера работ. В -й строке -мстолбце стоят затраты на выполнение -м кандидатом -й работы.

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

Алгоритм метода содержит следующие шаги.

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

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

Шаг 3.Поиск оптимального решения. Просматривают строку, содержащую наименьшее число нулей. Отмечают один из нулей этой строки и зачеркивают все остальные нули этой строки и того столбца, в котором находится отмеченный нуль. Аналогичные опе­рации последовательно проводят для всех строк. Если назначение, которое получено при всех отмеченных нулях, является полным (т.е. число отмеченных нулей равно ), то решение является опти­мальным, в противном случае следует переходить к шагу 4.

Шаг 4.Поиск минимального набора строк и столбцов, содержащих все нули.

Для этого необходимо отметить:

1) все строки, в которых не имеется ни одного отмеченного нуля;

2) все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных строк;

3) все строки, содержащие отмеченные нули хотя бы в одном из отмеченных столбцов.

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

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

Шаг 5.Перестановка некоторых нулей.

Взять наименьшее число из тех клеток, через которые проведены прямые. Вычесть его из каждого числа, стоящего в невычеркнутых столбцах и прибавить к каждому числу, стоящему в вычеркнутых строках. Эта операция не изменяет оптимального решения, после чего весь цикл расчета повторить, начиная с шага 3.

Задача о рюкзаке.

Задача о загрузке (задача о рюкзаке) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д. Задача о ранце – одна из задач комбинаторной оптимизации. Классическая задача о ранце известна очень давно. Вот её постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W – вместимость ранца.

Пример: Задание. В рюкзак объема V = 7 кладут N = 5 предметов.Объемы, веса и количество предметов в каждой группе приведены в таблице.

Объем
Вес
Кол-во

 

Максимизировать общий вес рюкзака.

Решение.

I этап. Условная оптимизация.
f1(L) = max(2x1); 0 < x1 < 1; x1 = 0,1.
f1(0) = max[0*2] = 0
f1(1) = max[0*2, 1*2] = 2
f1(2) = max[0*2, 1*2] = 2
f1(3) = max[0*2, 1*2] = 2
f1(4) = max[0*2, 1*2] = 2
f1(5) = max[0*2, 1*2] = 2
f1(6) = max[0*2, 1*2] = 2
f1(7) = max[0*2, 1*2] = 2

Таблица 1 – Расчет значения функции f1(L)

L
f1(L)
x1

f2(L) = max[3x2 + f1(L - 2x2)]; 0 < x2 < 3; x2 = 0,1,2,3.
f2(0) = max[0*3+0] = 0
f2(1) = max[0*3+2] = 2
f2(2) = max[0*3+2, 1*3+0] = 3
f2(3) = max[0*3+2, 1*3+2] = 5
f2(4) = max[0*3+2, 1*3+2, 2*3+0] = 6
f2(5) = max[0*3+2, 1*3+2, 2*3+2] = 8
f2(6) = max[0*3+2, 1*3+2, 2*3+2, 3*3+0] = 9
f2(7) = max[0*3+2, 1*3+2, 2*3+2, 3*3+2] = 11
Таблица 2 – Расчет значения функции f2(L)

 

L
f2(L)
x2

 

f3(L) = max[2x3 + f2(L - 3x3)]; 0 < x3 < 3; x3 = 0,1,2,3.
f3(0) = max[0*2+0] = 0
f3(1) = max[0*2+2] = 2
f3(2) = max[0*2+3] = 3
f3(3) = max[0*2+5, 1*2+0] = 5
f3(4) = max[0*2+6, 1*2+2] = 6
f3(5) = max[0*2+8, 1*2+3] = 8
f3(6) = max[0*2+9, 1*2+5, 2*2+0] = 9
f3(7) = max[0*2+11, 1*2+6, 2*2+2] = 11
Таблица 3 – Расчет значения функции f3(L)

L
f3(L)
x3


f4(L) = max[4x4 + f3(L - 1x4)]; 0 < x4 < 1; x4 = 0,1.
f4(0) = max[0*4+0] = 0
f4(1) = max[0*4+2, 1*4+0] = 4
f4(2) = max[0*4+3, 1*4+2] = 6
f4(3) = max[0*4+5, 1*4+3] = 7
f4(4) = max[0*4+6, 1*4+5] = 9
f4(5) = max[0*4+8, 1*4+6] = 10
f4(6) = max[0*4+9, 1*4+8] = 12
f4(7) = max[0*4+11, 1*4+9] = 13
Таблица 4 – Расчет значения функции f4(L)

L
f4(L)
x4


f5(L) = max[1x5 + f4(L - 1x5)]; 0 < x5 < 2; x5 = 0,1,2.
f5(0) = max[0*1+0] = 0
f5(1) = max[0*1+4, 1*1+0] = 4
f5(2) = max[0*1+6, 1*1+4, 2*1+0] = 6
f5(3) = max[0*1+7, 1*1+6, 2*1+4] = 7
f5(4) = max[0*1+9, 1*1+7, 2*1+6] = 9
f5(5) = max[0*1+10, 1*1+9, 2*1+7] = 10
f5(6) = max[0*1+12, 1*1+10, 2*1+9] = 12
f5(7) = max[0*1+13, 1*1+12, 2*1+10] = 13
Таблица 5 – Расчет значения функции f5(L)

L
f5(L)
x5

II этап. Безусловная оптимизация.
Таким образом, максимальный вес рюкзака f5(7) равна 13 кг.
При этом x5 = 0, так как f5(7) = 13 достигается при х5=0 (см. таблицу 5).
Предметы остальных типов распределяются следующим образом:
L = 7 - 1 * 0 = 7
f4(7) = 13 достигается при х4 = 1 (см. таблицу 4).
L = 7 - 1 * 1 = 6
f3(6) = 9 достигается при х3 = 0 (см. таблицу 3).
L = 6 - 3 * 0 = 6
f2(6) = 9 достигается при х2 = 3 (см. таблицу 2).
L = 6 - 2 * 3 = 0
f1(0) = 0 достигается при х1 = 0 (см. таблицу 1).
L = 0 - 1 * 0 = 0
В итоге наилучший вариант загрузки рюкзака достигается при значениях: x1 = 0, x2 = 3, x3 = 0, x4 = 1, x5 = 0

Задача оптимального раскроя  

Рассмотрим задачу оптимального линейного раскроя.

Есть достаточно большое число одномерных заготовок одинаковой длины D = 2,6 м. Заготовки следует разрезать на детали 3 типов длиной L = (1,5; 0,9; 1,2). По данным числамD и Li составить матрицу всех возможных способов раскроя A = aij, где каждое aij указывает количество деталей i типа, что выходит из одной заготовки при раскрое по jспособому, если заданы также потребности B = (45, 74, 66), в деталях i типа.
Составить математическую модель и решить задачу линейного программирования для выполнения планового задания, раскроив минимальное число заготовок.

Решение

Составим таблицу исходных данных:

i Li Bi
1,5
0,9
1,2


Заполним матрицу всех возможных способов раскроя, учтя длину заготовок D = 2,6 м:

Длина раскроев Способы раскроя
1 2 3 4
1,5
0,9
1,2


Таким образом, матрица A следующая:

Получим задачу целочисленного линейного программирования:

z = x1 + x2 + x3 + x4min


x1, x2, x3, x4 > 0

1) Первый этап

Найдем решение, отбросив условие целочисленности. Изменим знаки целевой функции на противоположные и будем рассматривать задачу на максимум:
z = - x1 - x2 - x3 - x4max

Сведем задачу к каноническому виду, для чего прибавим дополнительные или базисные векторы [АКУ, с. 12]:

Для увеличения количества базисных векторов отнимаем от строки, которая содержит отрицательную вспомогательную переменную и максимальный B2 = 74 все строки с отрицательными вспомогательными переменными (1, 3) [ГЕТ, с. 177].

Поскольку начальный план нельзя построить обычным образом, используем метод искусственного базиса [АКУ, с. 47].
Вектор z1 является искусственным.

Тогда целевая функция запишется так:

z = - x1 - x2 - x3 - x4Mz1max ,

где M - большое число.

Построим начальную симплекс-таблицу, где
Q - неотрицательное отношение столбца плана к ключевому столбцу.

Базис Cб План -1 -1 -1 -1 -M Q
x1 x2 x3 x4 x5 x6 x7 z1
x5 -1 29/2
z1 -M -1
x7 -2 -1
Δj
-74 -1 -2 -1


Cтолбик 2 есть ключевым, поскольку он содержит минимальный отрицательный элемент

Δ2 = -2M + 1.

Строка 3 есть ключевой, поскольку в ней минимальное Q3 = 4.
Ключевой элемент находится на их пересечении и равный числу 2.
Вместо вектора x7, который удаляем из базиса, вводим вектор x2.
Делим ключевую строку на ключевой элемент 2.
Умножаем его на -1 и добавляем к 4 строке.
Умножаем его на -2 и добавляем к 1 строке.
Умножаем его на -2 и добавляем к 2 строке.
Получим следующую симплекс-таблицу.

Базис Cб План -1 -1 -1 -1 -M Q
x1 x2 x3 x4 x5 x6 x7 z1
x5 -1 -1 21/2
z1 -M -1
x2 -1 1/2 -1 -1/2 1/2
Δj -4 1/2 1/2 -1/2
-66 -1 -2


Cтолбик 4 есть ключевым, поскольку он содержит минимальный отрицательный элемент Δ4 = -2M + 2.

Строка 1 есть ключевой, поскольку в ней минимальное Q1 = 21/2.
Ключевой элемент находится на их пересечении и равный числу 2.
Вместо вектора x5, который удаляем из базиса, вводим вектор x4.
Делим ключевую строку на ключевой элемент 2.
Умножаем его на -2 и добавляем к 4 строке.
Умножаем его на -2 и добавляем к 2 строке.
Умножаем его на 1 и добавляем к 3 строке.
Получим следующую симплекс-таблицу.

Базис Cб План -1 -1 -1 -1 -M Q
x1 x2 x3 x4 x5 x6 x7 z1
x4 -1 21/2 -1/2 1/2 1/2 -1/2
z1 -M -1
x2 -1 29/2 1/2 1/2 -1/2
Δj -25 3/2 -1 1/2 1/2
-45 -1


Cтолбик 1 есть ключевым, поскольку он содержит минимальный отрицательный элемент Δ1 = -M + 3/2.
Строка 2 есть ключевой, поскольку в ней минимальное Q2 = 45.
Ключевой элемент находится на их пересечении и равный числу 1.
Вместо вектора z1, который удаляем из базиса, вводим вектор x1. Дальше из расчетов данную искусственную переменную исключаем.
Делим ключевую строку на ключевой элемент 1.
Умножаем его на -3/2 и добавляем к 4 строке.
Умножаем его на 1/2 и добавляем к 1 строке.
Получим следующую симплекс-таблицу.

Базис Cб План -1 -1 -1 -1 Q
x1 x2 x3 x4 x5 x6 x7
x4 -1 1/2 -1/2
x1 -1 -1
x2 -1 29/2 1/2 1/2 -1/2
Δj -185/2 1/2 1/2 1/2


Поскольку содержится нуль в небазисном векторе x3, то существует еще одно оптимальное решение, которое также найдем. Строка 3 есть ключевой, поскольку в ней минимальное Q3 = 29.
Ключевой элемент находится на их пересечении и равный числу 1/2.
Вместо вектора x2, который удаляем из базиса, вводим вектор x3.
Делим ключевую строку на ключевой элемент 1/2.
Умножаем его на -1/2 и добавляем к 1 строке.
Получим окончательную симплекс-таблицу.

Базис Cб План -1 -1 -1 -1
x1 x2 x3 x4 x5 x6 x7
x4 -1 37/2 -1 -1/2 1/2 -1/2
x1 -1 -1
x3 -1 -1
Δj -185/2 1/2 1/2 1/2


Последняя строка таблицы не содержит отрицательных элементов, следовательно найденное решение является оптимальным: X = (45, 0, 29, 37/2), zmax = -185/2.
Вернувшись к замене знака функции, получим: zmin = 185/2.

Решение имеет дробные значения, поэтому переходим ко 2 этапу.

2) Второй этап

Применим метод Гомори для поиска целочисленного решения [АКУ, с. 180].
Дополнительные ограничения строятся по формуле на основании строки,
переменная плана которого имеет наибольшую дробную часть.
Вычислим дробные части основных переменных плана: f1(x4) = 0,5000.
Неравенство строим на основании 1 строки




Добавляем уравнение к системе уравнений и строим симплекс-таблицу с новым ограничением.
Новую задачу решаем двойственным симплекс-методом [АКУ, с. 107].

Базис Cб План -1 -1 -1 -1
x1 x2 x3 x4 x5 x6 x7 x8
x4 -1 37/2 -1 -1/2 1/2 -1/2
x1 -1 -1
x3 -1 -1
x8 -1/2 -1/2 -1/2 -1/2
Δj 185/2 1/2 1/2 1/2


Строка 4 является ключевой, поскольку она содержит минимальный элемент плана: x8 = -1/2.
Cтолбик 5 является ключевым, поскольку в нем минимальное двойственное отношение:
Ключевой элемент находится на их пересечении и равен числу -1/2.
Выполняем преобразование таблицы симплексным методом.
Вместо вектора x8, который удаляем из базиса, вводим вектор x5.
Делим ключевую строку на ключевой элемент -1/2.
Умножаем его на -1/2 и добавляем к 5 строке.
Умножаем его на 1/2 и добавляем к 1 строке.
Умножаем его на 1 и добавляем к 2 строке.
Умножаем его на -1 и добавляем к 3 строке.
Поскольку отрицательного числа в плановом столбце не существует, получим окончательный план.
Занесем его в симплекс-таблицу.

Базис Cб План -1 -1 -1 -1
x1 x2 x3 x4 x5 x6 x7 x8
x4 -1 -1 -1
x1 -1 -1
x3 -1 -2 -1
x5 -2
Δj -93


Поскольку базисные переменные приобрели целые значения, то задача решена.
Последняя строка таблицы не содержит отрицательных элементов, следовательно найденное решение является оптимальным: X = (46, 0, 28, 19), zmax = -93.
Вернувшись к замене знака функции, получим: zmin = 93.
Таким образом, для использования минимального количества заготовок необходимо 1 способом разрезать 46, 3 способом - 28 и 4 способом - 19 заготовок.

Ответ: X = (46, 0, 28, 19), zmin = 93.





Последнее изменение этой страницы: 2016-04-07; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.227.247.17 (0.017 с.)