Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Нахождение опорного решения методом северо-западного угла
|
|
Исходные данные занесем в упрощенную таблицу
В первом столбце указаны мощности поставщиков, в первой строке – спрос потребителей. Числа в левом верхнем углу клетки – это стоимость перевозок единицы груза от соответствующего поставщика к соответствующему потребителю, т.е. значения из данной в условии матрицы.
План перевозок будет задан, если мы укажем, сколько единиц груза должен получить каждый потребитель от каждого поставщика, т.е. если пустая таблица из трех строк и четырех столбцов будет заполнена.
Северо-западный угол таблицы – это её левый верхний угол, т.е. клетка в 1-й строке и 1-м столбце – клетка (1,1). Поэтому рассмотрим 1-го поставщика и 1-го потребителя. У поставщика А1 есть 30 единиц груза, а потребителю В1 нужно 70 единиц. Находим минимум из этих двух чисел: min (30,70) = 30. Клетка (1,1) перечеркивается по диагонали сплошной чертой (), по центру пишется найденный минимум 30. Это означает, что А1 должен поставить потребителю В1 30 единиц груза. Такие клетки в дальнейшем будем называть отмеченными.
Так как поставщик А1 израсходовал все свои 30 единиц груза, то мы исключаем его из рассмотрения. Поэтому все остальные клетки 1-й строки перечеркиваем по диагонали. Такие клетки в дальнейшем будем называть пустыми.
После первого шага наша таблица имеет следующий вид:
| 304 | ||||
Первая строка в дальнейшем не рассматривается.
Северо-западный угол этой таблицы – это клетка (2,1). Поэтому рассмотрим 2-го поставщика и 1-го потребителя. Мощность поставщика А2 равна 190 единиц. Спрос потребителя В1 – 70 единиц груза. Но 30 единиц груза он получил от поставщика А1 (об этом говорит отмеченная клетка (1,1)). Поэтому непокрытый спрос потребителя В1 равен 70–30=40. Находим минимум min (190,70-30)=40. Клетка (2,1) становится отмеченной. Мы запишем там этот минимум 40.
Поставщик А1(30 единиц) и А2 (40 единиц) полностью покрывают спрос потребителя В1 (70 единиц). Поэтому остальные клетки 1-го столбца объявим пустыми и в дальнейшем исключим из рассмотрения.
После второго шага таблица имеет следующий вид:
| 304 | ||||
| 403 | 1 | |||
Северо-западный угол этой таблицы – это клетка (2,2). min (190-40,120)=120.
Получаем следующую таблицу:
| 304 | ||||
| 403 | 1201 | |||
Северо-западный угол этой таблицы – это клетка (2,3). min (190-40-120,150)=30. Получаем следующую таблицу:
| 304 | ||||
| 403 | 1201 | 302 | ||
Северо-западный угол этой таблицы – это клетка (3,3). min (250, 150-30)=120. Получаем следующую таблицу:
| 304 | ||||
| 403 | 1201 | 302 | ||
| 1203 |
Осталась одна незаполненная клетка – это клетка (3,4). min (250-120,130)=130. Получаем следующую таблицу:
| 304 | ||||
| 403 | 1201 | 302 | ||
| 1203 | 1307 |
После выполнения очередного шага мы исключали из рассмотрения либо строку, либо столбец. Только на последнем шаге отпали и строка, и столбец. Поэтому для полностью заполненной таблицы должно соблюдаться следующее отношение: число отмеченных клеток = число строк +число столбцов – 1. В нашем случае это так: 6=3 + 4 – 1.
Посчитаем суммарные затраты. Для этого нужно в каждой отмеченной клетке перемножить ее числа и результаты сложить: 4*30+3*40+1*120+2*30+3*120+7*130=1690.
Date: 2015-07-27; view: 469; Нарушение авторских прав