Контрольная работа: Автоматизация системного проектирования
Находим максимальный элемент первого столбца – 3. Отнимаем из него все элементы этого столбца. Аналогично для получения второго, третьего и четвертого столбцов новой матрицы отнимаем все элементы этих столбцов от 6, 6 и 10 соответственно. Получим матрицу С' (C' ~C).
| 0 | 4 | 0 | 3 |
| 1 | 3 | 2 | 5 |
| 2 | 0 | 4 | 5 |
| 1 | 2 | 2 | 0 |
Т.к. в каждом ряду С' кроме второго есть нуль, поэтому отнимаем лишь минимальный элемент второго ряда (1) от всех элементов этого ряда и получаем матрицу З0 ~ С' и на этом процесс приведения матрицы заканчивается.
(+) + +
  0* | 4 | 0 | 3 + |
| 0 | 2 | 1 | 4 |
| 2 | 0* | 4 | 5 |
| 1 | 2 | 2 | 0* |
Далее ищем и отмечаем знаком '*' независимые нули в З0, начиная с первого ряда.
Первая итерация. Первый этап
Выделяем знаком «+» первый, второй и четвертый столбец матрицы Зо , которые содержат 0*.
Пересмотрим невыделенный третий столбец, находим в нем невыделенный нуль IЗ43 =0, отмечаем его штрихом и выделяем знаком «+» первый ряд.
Ищем минимальный элемент в невыделенной части матрицы Зо (т.е. элементы, которые находятся в столбцах и рядах, не обозначенных знаком «+»).
Вторая итерация. Первый этап
Просматривая все невыделенные элементы, находим среди них невыделенный нуль IЗ12 =0, отмечаем его знаком штрих и переходим ко второму этапу.
+ +
Второй этап. Начиная с элемента IЗ12 =0, строим цепь двигаясь от него по столбцу. Находим нуль со звездочкой IЗ11 =0*, далее двигаясь по первому ряду и находим 0 (IЗ13 ).
Таким образом, цепь построенная 0'21 -0* 11- 0'13. Заменяем штрих на звездочку и сокращаем звездочки над парными элементами цепи, а так же все знаки выделения столбцов и рядов. После этой итерации количество независимых нулей (0*) стало равняться 4 (размерности матрицы З) и поэтому алгоритм заканчивает работу.
Искомые элементы назначения отвечают позициям независимых нулей матрицы Зз (т.е. )*0.
| 0, | 4 | 0* | 3 |
| 0* | 2 | 1 | 4 |
| 2 | 0* | 4 | 5 |
| 1 | 2 | 2 | 0* |
Соответствующее значение целевой функции:
F = C12 + C23 + C31 + C44 = 2 + 6 + 6 + 10 = 24.
1.2 Решить задачу линейного программирования, используя
табличный симплексный метод
Предприятию необходимо выпустить 2 вида изделий (Р1; Р2). Есть 3 вида станков (Т1; Т2; Т3), каждый из которых может обрабатывать изделия всех видов.
Продолжительность обработки
на станке 1-го типа изделий 1-го типа 4 единицы
на станке 2-го типа изделий 1-го типа 1 единица
на станке 3-го типа изделий 1-го типа 1 единица
на станке 1-го типа изделий 2-го типа 0 единиц
на станке 2-го типа изделий 2-го типа 2 единицы
на станке 3-го типа изделий 2-го типа 4 единицы
Доход от реализации изделия первого типа составляет 6 единиц, второго типа – 6 единиц.
Запас мощности (рабочее время станка) 1-о типа – 20 единиц, 2-го типа 37 единиц, 3-го типа – 40 единиц.
Составить такой план загрузки станков, при котором себестоимость выпуска продукции будет минимальной.