Курсовая работа: Решение задач линейного программирования транспортной задачей
Камни – заполненные ячейки
· Поставим знак «+», в ячейку которую оцениваем;
· Двигаясь горизонтально или вертикально к заполненной ячейке(при этом можем пропустить заполненную или пустую ячейку которая, разрешит следующий переход к заполненной ячейке), поставим знак «-»;
· Изменяем направление и перемещаемся к другой заполненной ячейке, выбираем ту разрешит следующий переход, ставим в нее знак «+»;
· Процесс перемещения в заполненной ячейке и чередование знаков продолжаем пока не вернемся к первоначальной.
Таблица 3
Оценивание ячеек
1-А | |
1А+4 | -8 3А |
3D+5 | -1 1D |
0 |
1-C | |
1C+7 | -1 1D |
3D+5 | -16 3C |
-5 |
Оценка пустых ячеек методами возможна при условии: число заполненных ячеек равна сумме строк и столбцов и -1:
k=R+L-1
Значение оценки показывает на сколько сократятся(увеличатся) затраты на перевозку единиц продукции если в эту ячейку переместить значение.
Выбираем из оценок наибольшее по модулю отрицательное значение. Из отрицательных выбираем наименьшее и вычитаем его из всех ячеек пути.
Таблица 4
Изменение начальной таблицы
4 | 7 | 7 | 1 | 100 | |||||
10 | 90 | ||||||||
12 | 3 | 8 | 8 | 200 | |||||
90 | 110 | ||||||||
8 | 10 | 16 | 5 | 150 | |||||
80 | 70 | ||||||||
80 | 90 | 120 | 160 |
Таким образом, производим решение, находя новое оптимальное решение пока все оценки пустых ячеек будут содержать только положительные значения и нули.
Метод MODI (модифицированное распределение).
Оценка пустых ячеек вычислением индексных значений строки и столбца.
Этот метод состоит из шагов:
1) Сделать начальное распределение (интуитивный подход), проверить матрицу на полноценность, в случае необходимости провести корректировку.
2) Получить номер индекса для каждой строки и столбца. Делая это используя только заполненные ячейки. Всегда есть по крайней мере одна заполненная ячейка в каждом столбце и строке.
а) начинаем, назначая ноль в первой строке
б) определить индекс столбца для любой заполненной ячейки в строке 1, используя следующие соотношения:
индекс столбца = U;
индекс строки = V;
затраты ячейки = С;
U = C-V
в) Каждое новое значение столбца позволит вычислить по крайней мере 1 новое значение строки и наоборот. Продолжайте эту процедуру пока все строки и столбцы будут заполнены индексами.
3) Получить оценки для пустых ячеек
W – оценка ячейки
W = C- (U+V)