КОНТРОЛЬНАЯ РАБОТА
по дисциплине
« ОПТИМИЗАЦИЯ ОРГАНИЗАЦИОННЫХ РЕШЕНИЙ»
Задание №1
Решение задачи об оптимальном направлении капиталовложений в строительную отрасль и оптимизации поставки строительных грузов
Определить наиболее экономичный вариант прироста мощности (строительства или реконструкции) и одновременно рассчитать оптимальный план перевозок строительной продукции до потребителя.
Решение
Составим базисные планы:
а) метод северо-западного угла
Значение целевой функции:
L1 = 160 х 15 + 20 х 3 + 60 х 10 + 180 х 5 + 40 х 16 + 40 х 0 =
= 2 400 + 60 + 600 + 900 + 640 + 0 = 4 600 у. е.
б) метод двойного предпочтения
Значение целевой функции:
L2 = 180 х 3 + 160 х 3 + 60 х 5 + 20 х 0 + 40 х 5 + 20 х 13 + 20 х 0 =
= 540 + 480 + 300 + 0 + 200 + 260 + 0 = 1 780 у. е.
в) метод аппроксимации Фогеля
Значение целевой функции:
L3 = 160 х 3 + 180 х 3 + 20 х 10 + 60 х 5 + 40 х 5 + 40 х 0 =
= 480 + 540 + 200 + 300 + 200 + 0 = 1 720 у. е.
Проведем проверку матрицы на вырождение:
N – число занятых клеток матрицы, N = 6.
N = m + n – 1 = 4 + 4 – 1 = 7.
6 ≠ 7.
Следовательно, матрица – вырожденная, поэтому в одну из свободных ячеек в зоне вырождения вводим условную нулевую поставку груза.
Оптимальный план находим на основании базисного плана, построенного методом аппроксимации Фогеля, так как этот план имеет минимальную целевую функцию.
Проверим матрицу на оптимальность с помощью потенциалов строк u и столбцов v.
Потенциалы определим по занятым клеткам матрицы, тем самым соблюдая условие оптимальности (cij = uij + vij).
$IMAGE6$
Произведем проверку свободных клеток базисного плана на оптимальность.
| Коды свободных клеток | Δ = cij – (vij + uij) | Примечание |
| A-I | 15 – (1 + 0) = 15 | >0 |
| A-II | 18 – (8 + 0) = 10 | >0 |
| A-IV | 0 – (-2 + 0) = 2 | >0 |
| B-I | 12 – (1 – 3) = 14 | >0 |
| B-III | 16 – (3 – 3) = 16 | >0 |
| B-IV | 0 – (-2 + 2) = 0 | =0 |
| Г-I | 17 – (1 + 2) = 14 | >0 |
| Г-II | 13 – (8 + 2) = 3 | >0 |
| Г-III | 15 – (3 + 2) = 10 | >0 |
В данном случае все значения Δ ≥ 0, следовательно, составленный план неоптимален, переходим к улучшенному плану перевозок. В этом случае среди незагруженных клеток, для которых Δ ≥ 0, находим клетку с наибольшей величиной превышения стоимости (B-III).
Строим замкнутый контур, начиная перемещаться из потенциальной клетки.
$IMAGE7$
Контур распределения:
$IMAGE8$
Составим новый план распределения.
$IMAGE9$
Его целевая функция:
L4 = 160 х 3 + 180 х 3 + 60 х 10 + 20 х 5 + 40 х 16 + 40 х 0 =
= 480 + 540 + 600 + 100 + 640 + 0 = 2 360 у. е.
Проверяем полученную матрицу на оптимальность.
| Коды свободных клеток | Δ = cij – (vij + uij) | Примечание |
| A-I | 15 – (1 + 0) = 15 | >0 |
| A-II | 18 – (8 + 0) = 10 | >0 |
| A-IV | 0 – (-2 + 0) = 2 | >0 |
| B-I | 12 – (1 – 3) = 14 | >0 |
| B-II | 5 – (8 + 13) = -16 | <0 |
| B-IV | 0 – (-2 + 13) = -11 | <0 |
| Г-I | 17 – (1 + 2) = 14 | >0 |
| Г-II | 13 – (8 + 2) = 3 | >0 |
| Г-III | |