Работа рассчитана на 2 аудиторных часа. Необходимо получить пять видов различных вязкостных характеристик (V1, V2, V3, V4, V5) на тестомесильной машине

Пример 3.

Необходимо получить пять видов различных вязкостных характеристик (V1, V2, V3, V4, V5) на тестомесильной машине, имеющей 7 скоростей вращения месильной лопасти (P1, P2, P3, P4, P5, P6, P7). Результаты тестирования каждого вида теста, на соответствующие скорости вращения лопасти, даны в виде матрицы - С (тестирование производилось по десятибалльной системе).

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

Рис. 3.1.

Математическая модель задачи.

Переменные задачи.

Ведем переменные x_ij, принимающие два значения:

x_ij = 0, если i -й вид теста (P_i) не будет замешиваться на j -й скорости (V_j).

x_ij = 1, если i -й вид теста (P_i) будет замешиваться на j -й скорости (V_j).

i = 1, 2,... 7; j = 1, 2,... 5.

Ограничения на переменные задачи.

Очевидно, что все переменные задачи неотрицательные и целые числа: x _ij 0 и x _ij - целые.

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

, j =1, 2,... 7,

, i =1, 2,... 5,

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

Целевая функция в задаче о назначениях.

Необходимо выбрать скорости вращения лопасти так, чтобы суммарное число баллов, удовлетворяющее реологическим требованиям теста, было бы максимальным. Суммарное число баллов вычисляется по формуле:

;

Z = c₁₁ x ₁₁+c₁₂ x ₁₂+...+c₇₅ x ₇₅=7 x ₁₁+5 x ₁₂+...+4 x ₇₅;

Окончательная математическая модель задачи записывается так:

найти max ;

при ограничениях:

x_ij 0 и x_ij - целые числа, i =1, 2,... 7; j = 1, 2,... 5;

, j = 1, 2,... 7;

, i = 1, 2,... 5.

Таким образом, задача о назначениях есть частный случай транспортной задачи (см. пример 2).

Задание 1. Решение задачи о назначениях при помощи преобразования матрицы (С).

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

Задача нахождения минимального значения функции Z эквивалентна задаче нахождения минимума для функции , матрица (-С) имеет вид:

-

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

В каждой строке (С) и в каждом столбце образуют нули, вычитая минимальные элементы из соответствующих строк или столбцов. Если среди нулевых элементов матрицы (С) можно получить допустимое [5] решение задачи, то оно является оптимальным.

В рассматриваемом примере в каждой строке матрицы (С) нули есть (они появились в результате добавления фиктивных видов теста). Чтобы образовать нули в первых пяти столбцах матрицы (-С), определяем минимальные элементы в этих столбцах: -8, -9, -8, -9, -9 и вычитаем эти элементы из соответствующих столбцов матрицы. В результате получим следующую матрицу (рис. 3.2):

Рис. 3.2.

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

a) минимальным количеством горизонтальных и вертикальных прямых вычеркиваем все нули.

b) среди не вычеркнутых элементов находим минимальный элемент;

c) вычитаем минимальный элемент из всех вычеркнутых элементов;

d) к элементам, стоящим на пересечении вертикальных и горизонтальных прямых, прибавляем минимальный элемент.

Среди множества получаемых нулевых элементов определяем допустимое решение. Если допустимое решение найти нельзя, повторяем шаги a, b, c, d снова.

Процедура вычеркивания элементов и ее результат показаны на рис. 3.3. Минимальный элемент среди не вычеркнутых равен единице. На рис. 3.4 показан результат после вычитания единицы из не вычеркнутых элементов и прибавления единицы к элементам, стоящим на пересечении прямых. Допустимое решение соответствует отмеченным элементам.

Рис. 3.3.

Рис. 3.4

Перенеся полученное решение на исходную матрицу (С) (рис. 3.5)

Рис. 3.5.

получим, что скорости вращения лопасти Р1 и Р7 попадают на фиктивные виды теста и не используются при замесах необходимых видов теста. Скорость Р2 используется для пятого вида теста, Р3 - для первого, Р4 - для третьего, Р5 - для четвертого, Р6 - для второго. Сумма баллов, полученная при данном решении равна: 9 + 8 + 8 + 9 + 8 = 42.

Задание 2. Решение задачи в процедуре EXCEL «Поиск решения»

1) Ввод данных. Переносим данные задачи в MS EXCEL, при этом нужно ввести 2 столбца (6-ой и 7-ой) с нулевыми значениями для сбалансирования задачи. Результаты заполнения таблицы MS EXCEL представлены на рис. 3.6.

Рис. 3.6.

В ячейках B4: F10 введены результаты тестирования реологических характеристик теста, а в ячейках G4: H10 введены нули, что соответствует фиктивным видам теста.

Ячейки B14: F20 являются изменяемыми ячейками для данной процедуры.

В ячейках B21: H21 находятся суммы значений соответствующих столбцов изменяемых ячеек. Так в ячейке B21 находится сумма ячеек B14: B20. Аналогично в ячейках:

в С21 находится сумма ячеек С14: С20;

в D21 находится сумма ячеек D14: D20;

в E21 находится сумма ячеек E14: E20;

в F21 находится сумма ячеек F14: F20.

в G21 находится сумма ячеек G14: G20;

в H21 находится сумма ячеек H14: H20.

В ячейках I14: I20 находятся суммы значений соответствующих строк изменяемых ячеек. Так в ячейке I14 находится сумма ячеек B14: H14. Аналогично в ячейках:

в I15 находится сумма ячеек B15: H15;

в I16 находится сумма ячеек B16: H16;

в I17 находится сумма ячеек B17: H17;

в I18 находится сумма ячеек B18: H18;

в I19 находится сумма ячеек B19: H19;

в I20 находится сумма ячеек B20: H20.

Целевая функция заносится в ячейку J3 и вычисляется по формуле «СУММПРОИЗВ(B4:H10;B14:H20)».

2) Заполнение окна процедуры «Поиск решения»:

целевая функция: J3;

значение целевой функции: max;

изменяемые ячейки: B14: H20;

ограничения задачи:

B21: H21 =1 и I14: I20 = 1(все свободные рабочие места должны быть заняты);

B14: F20 0 (изменяемые ячейки должны иметь положительные значения).

В окне «Параметры» установить «Линейная модель», что соответствует решению задачи симплекс-методом. Результаты заполнения окна показаны на рис. 3.7.

Рис. 3.7.

3) Выполнив процедуру «Поиск решения» мы получили в первоначальной таблице следующие результаты (рис. 3.8):

Рис.3.8.

Эти результаты совпадают с решением задачи, полученным преобразованием матрицы (С).

Контрольные вопросы

1. С помощью какого метода решается задача о назначениях?

2. При каких условиях удовлетворяются ограничения в задаче о назначениях?

3. Как записывается целевая функция и математическая модель в задаче о назначениях?

4. По какому правилу и почему необходимо преобразовывать матрицу (С)?

5. Каким образом образуются нули в строках матрицы (С)?

6. Каким образом образуются нули в строках матрицы (-С)?

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

8. Как находится допустимое решение задачи о назначениях?

Поиск по сайту: