Нахождение опорного плана по методу северо-западного
угла состоит в последовательном определении значений ,
начиная с
. После того как определено очередное
значение
, оно заносится в соответствующую клетку
, которая будет называться занятой.
1. Определяем элементы матрицы искомого опорного
плана, начиная с :
Занесем это значение в клетку (1, 1), и она станет занятой.
Первый столбец «закрыт» для заполнения в нем остальных клеток, а в первой строке осталось
невывезенных единиц
товаров.
2. Поэтому далее двигаемся по первой строке, заполняя на следующем шаге следующую соседнюю клетку (1,2),
.
3. Второй столбец «закрыт» для заполнения в нем остальных клеток, а в первой строке осталось
невывезенных единиц
товаров.
4. Поэтому далее двигаемся по первой строке, заполняя на следующем шаге следующую соседнюю клетку (1,3),
.
5. Теперь «закрыта» первая строка (от первого поставщика весь товар вывезен), поэтому двигаемся по второму столбцу, полагая:
И, наконец,
.
В результате получим следующую таблицу:
|
60 |
70 |
110 |
150 |
|
|
|
90 |
|
|
|
Закрытым клеткам соответствуют базисные переменные, а свободным – свободные переменные.
Итак, найденный опорный план имеет вид:
Затраты составят:
Полученный план является допустимым и содержит занятых клеток, т.е. ранг системы
ограничений равен числу занятых клеток в опорном плане.
Опорный план, найденный методом северо-западного угла, не учитывает транспортные издержки, поэтому, значительно отличается от оптимального плана.
II. Метод минимального элемента.
Метод нахождения опорного плана, в котором учитываются транспортные издержки.
В этом методе заполняются последовательно клетки с
учетом минимальной стоимости перевозки, а
соответствующие величины
определяются точно так
же, как в методе северо-западного угла.
|
60 |
70 |
110 |
150 |
60 |
10 |
40 |
90 |
12 |
2 |
8 |
Заметим, что , т.е.
система ограничений совместна.
1. На первом шаге поставку делаем в клетку с
минимальными затратами. Поэтому нахождение опорного плана начинаем с поставки , так как
.
Величина определяется так же,
как и в методе северо-западного угла, т.е.:
.
Второй столбец «закрыт», а у второго поставщика осталось
невывезенных единиц
товаров.
Поэтому далее рассматриваем элементы второй строки.
2. Находим .
Определим .
«Закрыта» вторая строка, а третий потребитель недополучил 90 единиц товара.
3. Первый потребитель недополучил 60 единиц товара от А1 производителя.
Итак, таблица примет следующий вид:
|
60 |
70 |
110 |
150 |
|
|
|
90 |
|
|
|
Таким образом, получим опорный план:
,
который, приводит к затратам:
III. Решим задачу методом потенциалов.
Опорный план, полученный методом северо-западного угла имеет меньшие затраты, значит, он «лучший».
Опорный план, найденный методом северо-западного угла, выглядит следующим образом:
|
60 |
70 |
110 |
150 |
|
|
|
90 |
|
|
|
Проверим его на оптимальность.
Запишем систему потенциалов для заполненных клеток. Для этого, перепишем предыдущую таблицу, дополнив ее величинами ui и vj.
|
60 |
70 |
110 |
|
150 |
|
|
|
u1 |
90 |
|
|
|
u2 |
v1 |
v2 |
v3 |
1. По занятым клеткам опорного плана составим систему:
Система содержит 4 уравнения и 5 неизвестных. Положив,
например, , найдем:
;
;
;
;
2. Для всех свободных клеток проверим выполнение
условия . Имеем:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.