Htathfn

  • 26 апр. 2012 г.
  • 1340 Слова
Лабораторная работа № 1

Решение транспортной задачи методом
северо-западного угла

Цель работы:
1. Построить опорное решение транспортной задачи методом северо-западного угла.
2. Составить математическую модель задачи в соответствии со своим вариантом.
3. Результат решения транспортной задачи в MS Excel и сформулировать отчет, результаты которого сформированы в надстройке«Поиском решения». Пакета MS Excel.
В общем виде любая транспортная задача может быть задана в виде таблицы (см. табл. 1), с помощью которой формируется опорный план, а затем осуществляются преобразования с использованием метода северо-западного угла.
Таблица 1
Исходные данные к транспортной задаче
| 1 | 2 | … | n | |
1 | c11 | | x11 | c12 | | x12 | … | c1n | | x1n | a1 |
2 | c21 || x21 | c22 | | x22 | … | c2n | … | x2n | a2 |
... | | … | | | | | … | | | | |
m | cm1 | | x m1 | cm2 | | x m2 | … | cmn | | x mn | am |
| b1 | b2 | … | bn | d |

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

,

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

.

ПРИМЕР РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

Для иллюстрации использования метода северо-западного угла рассмотрим на конкретном примере все этапы решения транспортной задачи.
Задача. На двух складах А и В имеется соответственно 50 и 40 т груза. Требуется спланировать перевозки к трем потребителям С, D и E так, чтобы потребитель Сполучил 30 т, D – 20 т, E – 40 т, а затраты на перевозку были минимальными. Стоимость перевозки от складов к потребителям указана в табл. 2.
Таблица 2
Математическая модель для решения транспортной
задачи

Решение. Составим математическую модель этой задачи. На множестве решений системы

(1)
, то есть все значения должны быть неотрицательными.
Нужно найти минимальное значение целевойфункции
(2)
1. Составим методом северо-западного угла первое распределение поставок, начиная с заполнения верхней левой («северо-западной») клетки таблицы. Примем объем перевозки со склада А к потребителю С максимально возможным, исходя из условий задачи, равным 30. Потребитель С полностью удовлетворил свою потребность,...
tracking img