Метод «северо-западного угла».




Общая постановка транспортной задачи

Важным частным случаем задачи ЛП является транспортная задача.

Задача. Имеются 3 поставщика и 4 потребителя. В таблице приведены мощности поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик – потребитель».

  Поставщики Мощность поставщиков Потребители и их спрос
       
       
    х11 х12 х13 х14
    х21 х22 х23 х24
    х31 х32 х33 х34

В левом верхнем углу (i, j) клетки (i – номер строки, j - номер столбца) стоит коэффициент затрат (затраты на перевозку 1 ед. груза от i-го поставщика jтому потребителю). Необходимо найти объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку были бы минимальными.

Р е ш е н и е: построим экономико-математическую модель задачи. Искомый объем перевозки от i-того поставщика к j-тому потребителю обозначим через хij и назовем поставкой клетки (i; j). Объем груза, забираемого от 1-го, например, поставщика должен быть равен мощности этого поставщика – 60 ед. Значит х11 + х12 + х13 + х14 = 60. Аналогично – для других поставщиков. Получим систему:

Аналогично необходимо удовлетворить спрос каждого потребителя и получим систему

.

Очевидно, что объем перевозимого груза не может быть отрицательным. Поэтому хij 0. Суммарные затраты F на перевозку составят F = x11 + 2x12 + 5x12 + 3x14 + x21+ 6x22 + 5x23 + 2x24 + 6x31 + 3x32 + 7x33 + 4x34.

Тогда математическая формулировка задачи: на множестве неотрицательных решений системы ограничений найти такое решение Х = (x11, x12, …, x33, x34), при котором линейная функция F принимает минимальное значение.

Особенности экономико-математической модели транспортной задачи:

· система ограничений – система уравнений (т.е. задана в каноническом виде)

· коэффициенты при переменных системы ограничений равны 1 или 0

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

Сформулируем постановку транспортной задачи в общем виде. Пусть сij – коэффициенты затрат, Мi – мощности поставщиков, Nj – мощности потребителей, i = 1, …,m; j = 1, …,n; m –число поставщиков, n – число потребителей. Система ограничений примет вид ; ( 30 ) (31). Линейная функция F = (32).

Математическая формулировка транспортной задачи в общей постановке: на множестве неотрицательных (допустимых) решений системы ограничений (30) и (31) найти такое решение Х = (x11, x12, …, xmn), при котором значение линейной функции (32) минимально.

Произвольное допустимое решение Х = (x11, x12, …, xmn) системы ограничений (30) и (31) называют распределением поставок.

В рассмотренной выше задаче = . Задачи, удовлетворяющие этому условию, называют закрытыми. В противном случае модель и задача – открытая.

Решение транспортной задачи

Метод «северо-западного угла».

Одним из возможных методов нахождения первоначального базисного распределения поставок является метод «северо-западного угла».

Решим этим методом задачу п.1.2. Дадим переменной х11 максимально возможное значение (поставку в клетку (1,1) – «северо-западный» угол таблицы поставок): х11 = min{60, 20} = 20. после этого спрос 1-го потребителя удовлетворен полностью (клетки ниже перечеркнуты пунктиром).

       
  20      
         
         

В таблице поставок найдем новый «северо-западный угол» - клетка (1, 2) и дадим в нее максимально возможной значение. Учтем, что у первого поставщика осталось только 40 ед. товара, тогда х12 = min{40; 110} = 40. И мощность первого поставщика полностью реализована (клетки (1,3), (1,4) – пунктиром). Далее снова ищем «северо-западный угол» и действуем аналогично до заполнения всей таблицы. Суммарные затраты F = 20 + 80+420+ 200 + 20 + 400 = 1140.

Недостаток этого метода в том, что он не учитывает коэффициенты затрат.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-15 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: