Материал: Основы математического моделирования. методические указания к выполнению контрольной работы для студентов направления Машиностроение. Бырдин А.П., Костина Т.И

Таблица 6 Время выполнения операций подходящими

станками и время транспортировки

Рис. 2. Орграф для задачи нахождения кратчайшего пути

Произвольный путь на построенном орграфе из s в t проходит через промежуточные вершины ui1,1, vi1,1, ui2,2, vi2,2,....uin,n, ,vin,n, и обладает следующими свойствами:

а) он определяет вариант допустимого назначения операций на станки, поскольку i1,i2,...,in – это номера станков, которые должны выполнять операции O1,O2,...,On . Причем нет ни одного варианта допустимого назначения операций, которому не соответствовал бы некоторый путь из s в t.

б) соответствующий путь маршрут проходит станки в последовательности Ci1,Ci2,...,Cim. Самая длинная дуга пути определяет самый длительный по

26

транспортировка от станка Cik к станку Cik 1.

Пользуясь табл. 6, присваиваем дугам соответствующее время, например, если первую операцию выполнить на первом станке, то это займет 3 единицы времени, и т.д. Самым производительным является маршрут, который деталь проходит за минимальное время. Такая задача сводится к задаче нахождения кратчайшего пути. Поиск кратчайшего пути заключается в следующем: стартуя из вершины «» выбираем дуги с меньшим числом времени. Таким образом, ми-

Задача №4

Задание. Найти максимум целевой функции при заданных ограничениях.

Z(x) 9x1 5x2 4x3 3x4 2x5 max,

x1 2x2 2x3 6,x1 2x2 x3 x4 24,

2x1 x2 4x3 x5 30.

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

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

1.Привести задачу к каноническому виду.

2.Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решения ввиду несовместимости. Привести системы ограничений).

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

4.Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.

5.Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x6 с коэффициентом +1. В целевую функцию перемен-

ная x6 входит с коэффициентом ноль (т.е. не входит). Получаем:

27

Z(x) 9x1 5x2 4x3 3x4 2x5 0x6 max,

x1 2x2 2x3 x6 6,x1 2x2 x3 x4 24,

2x1 x2 4x3 x5 30,

xi 0, i.

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю: x1 x2 x3 0.

Получаем опорное решение Х1=(0,0,0,24,30,6) с единичным базисом Б1=( A4, A5, A6).

Составляем симплексную табл. 7. В столбец A0 записывается правая часть ограничений. С правой стороны записываются коэффициенты ограничений. Последняя строка - это целевая функция, умноженная на −1:

Базисные векторы A6, A4, A5 следовательно, все элементы в столбцах A6, A4, A5 ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца A4, кроме ведущего элемента. Для этого сложим строку 4 со строкой 2, умноженной на 3. Обнулим все элементы столбца A5, кроме ведущего элемента. Для этого сложим строку 4 со строкой 3, умноженной на 2.

Симплекс - таблица примет вид (табл. 8):

Таблица 8

В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях-ограничениях. В последней строке таблицы в столбце "A0" записываются значения целевой функции на опорном решении Z(x1).

28

Начальное опорное решение не является оптимальным, так как в задаче на максимум коэффициенты в 4 строке для векторов A1 и A3 отрицательные.

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

В качестве ведущего столбца выберем столбец A3, так как среди коэффициентов в последней строке, по модулю, наибольшим является число 9, max(2,3,9)=9, значит, в базис входит вектор A3. В качестве ведущей строки выберем строку 1, так как наименьшее из отношений элементов сводного столбца к соответствующим элементам ведущему столбца является 3, min (6/2,24/3,-)=3, значит из базиса выходит A6. Заметим, что при делении положительного элемента на отрицательный получается бесконечность. На пересечении ведущей строки и ведущего столбца находится ведущий элемент, равный 2.

Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 2, 3, 4 со строкой 1, умноженной на -1/2, 2, 9/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент. Симплекстаблица примет следующий вид (табл. 9):

Таблица 9

Это решение не является оптимальным, так как вектор A2 имеет отрицательное значение в 4 строке равное 6. Для улучшение решения необходимо ввести вектор A2 в базис опорного решения.

В качестве ведущего столбца выберем столбец A2, так как по модулю max(5/2,6)=6. В качестве ведущей строки выберем строку 2, так как min(-, 21/3, -)=7, заметим, что при делении положительного элемента на отрицательный получается бесконечность. На пересечении ведущей строки и ведущего столбца находится ведущий элемент, равный 3.

Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 1, 3, 4 со строкой 2, умноженной на 1/3, 1, 2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс-таблица примет следующий вид (табл. 10):

29

Таблица 10

Задача №5

Задание. На одном станке можно обрабатывать 5 видов деталей, затрачивая при этом одинаковое время на обработку одной детали каждого вида. В таблице задана длительность переналадки станка для обработки j–й детали по-

сле i–й детали, i 1,5, j 1,5. Требуется найти последовательность обработки деталей, имеющую минимальную суммарную длительность переналадки.

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

30