Составление математической модели задачи. Решение задачи линейного программирования графическим методом. Решение задачи симплекс-методом и с исполь­зованием компьютера (пакет Ехсеl), страница 4

Нахождение опорного плана по методу северо-западного угла состоит в последовательном определении значений , начиная с . После того как определено очередное значение , оно заносится в соответствующую клетку , которая будет называться занятой.

1. Определяем элементы матрицы искомого опорного плана, начиная с :

Занесем это значение в клетку (1, 1), и она станет занятой.

Первый столбец «закрыт» для заполнения в нем остальных клеток, а в первой строке осталось

 невывезенных единиц товаров.

2. Поэтому далее двигаемся по первой строке, заполняя на следующем шаге следующую соседнюю клетку (1,2),

.

3. Второй столбец «закрыт» для заполнения в нем остальных клеток, а в первой строке осталось

 невывезенных единиц товаров.

4. Поэтому далее двигаемся по первой строке, заполняя на следующем шаге следующую соседнюю клетку (1,3),

.

5. Теперь «закрыта» первая строка (от первого поставщика весь товар вывезен), поэтому двигаемся по второму столбцу, полагая:

И, наконец,

.

В результате получим следующую таблицу:

Закрытым клеткам соответствуют базисные переменные, а свободным – свободные переменные.

Итак, найденный опорный план имеет вид:

Затраты составят:

Полученный план является допустимым и содержит  занятых клеток, т.е. ранг системы ограничений равен числу занятых клеток в опорном плане.

Опорный план, найденный методом северо-западного угла, не учитывает транспортные издержки, поэтому, значительно отличается от оптимального плана.

II. Метод минимального элемента.

Метод нахождения опорного плана, в котором учитываются транспортные издержки.

В этом методе заполняются последовательно клетки с учетом минимальной стоимости  перевозки, а соответствующие величины  определяются точно так же, как в методе северо-западного угла.

Заметим, что , т.е. система ограничений совместна.

1. На первом шаге поставку делаем в клетку с минимальными затратами. Поэтому нахождение опорного плана начинаем с поставки , так как .

Величина  определяется так же, как и в методе северо-западного угла, т.е.:

.

Второй столбец «закрыт», а у второго поставщика осталось

 невывезенных единиц товаров.

Поэтому далее рассматриваем элементы  второй строки.

2. Находим .

Определим .

«Закрыта» вторая строка, а третий потребитель недополучил 90 единиц товара.

3. Первый потребитель недополучил 60 единиц товара от А₁ производителя.

Итак, таблица примет следующий вид:

Таким образом, получим опорный план:

,

который, приводит к затратам:

III. Решим задачу методом потенциалов.

Опорный план, полученный методом северо-западного угла имеет меньшие затраты, значит, он «лучший».

Опорный план, найденный методом северо-западного угла, выглядит следующим образом:

Проверим его на оптимальность.

Запишем систему потенциалов для заполненных клеток. Для этого, перепишем предыдущую таблицу, дополнив ее величинами u_i и v_j.

1. По занятым клеткам опорного плана составим систему:

Система содержит 4 уравнения и 5 неизвестных. Положив, например, , найдем:

;

;

;

;

2. Для всех свободных клеток проверим выполнение условия . Имеем: