Решение транспортных задач (стр. 4 из 5)
Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейно независимы.
Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому, опорное решение, построенное по данному методу, может быть далеким от оптимального.
Пример 3:
Составить опорное решение методом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5 потребителей. данные записаны в таблице 6
Таблица 6
  | В150 | В240 | В330 | В420 | В510 |
| А110 | |||||
| А220 | |||||
| А330 | |||||
| А440 | |||||
| А550 |
Решение:
Распределяем запасы первого поставщика. Так как его запасы
меньше запросов первого потребителя 
, то в клетку (1,1) записываем перевозку 
и исключаем из рассмотрения первого поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя 
.Распределяем запасы второго поставщика. Так как его запасы
, меньше запросов первого потребителя 
, то записываем в клетку (2,1) перевозку 
и исключаем из рассмотрения второго поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя 
.Распределяем запасы третьего поставщика
. Так как его запасы больше запросов первого потребителя 
, то записываем в клетку (3,1) перевозку 
и исключаем из рассмотрения первого потребителя. Определяем оставшиеся неудовлетворенными запросы третьего поставщика 
.Распределяем запасы третьего поставщика
. Так как его запасы меньше запросов второго потребителя 
, то в клетку (3,2) записываем перевозку 
и исключаем из рассмотрения третьего поставщика. Определяем оставшиеся неудовлетворенными запросы второго потребителя 
.Распределяем запасы четвертого поставщика
. Так как его запасы больше запросов второго потребителя 
, то записываем в клетку (4,2) перевозку 
и исключаем из рассмотрения второго потребителя. Определяем оставшиеся неудовлетворенными запросы четвертого поставщика 
.Распределяем запасы четвертого поставщика
. Так как его запасы меньше запросов третьего потребителя 
, то в клетку (4,3) записываем перевозку 
и исключаем из рассмотрения четвертого поставщика. Определяем оставшиеся неудовлетворенными запросы третьего потребителя 
.Распределяем запасы пятого поставщика. Так как его запасы
больше запросов третьего потребителя 
, то в клетку (5,3) записываем перевозку 
и исключаем из рассмотрения третьего потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика 
.Распределяем запасы пятого поставщика. Так как его запасы
больше запросов четвертого потребителя 
, то в клетку (5,4) записываем перевозку 
и исключаем из рассмотрения четвертого потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика 
.Распределяем запасы пятого поставщика. Так как его запасы
равны запросам пятого потребителя 
, то в клетку (5,5) записываем перевозку 
и исключаем из рассмотрения пятого поставщика и пятого потребителя.Ввиду того, что задача с правильным балансом, запасы всех поставщиков исчерпаны и запросы всех потребителей удовлетворены.
Результаты построения опорного решения приведены в таблице 7.
  | В150 | В240 | В330 | В420 | В510 |
| А110 | 10 | - | - | - | - |
| А220 | 20 | - | - | - | - |
| А330 | 20 | 10 | - | - | - |
| А440 | - | 30 | 10 | - | - |
| А550 | - | - | 20 | 20 | 10 |
1.3 БЛОК-СХЕМА (АЛГОРИТМ РЕШЕНИЯ)
 |
нет нет
да
Метод
северо-
- западного
угла
метод
потенциалов
2. ФОРМЫ ВХОДНОЙ ИНФОРМАЦИИ
Входные данные вводятся с клавиатуры
· Запасы i-го поставщика
· запросы j-го потребителя
В данном примере
· запасы поставщиков(10; 20; 30; 40; 50)
· запросы потребителей(50; 40; 30; 20; 10)
3. ФОРМЫ ВЫХОДНОЙ ИНФОРМАЦИИ
Информация выводится на экран в виде таблицы с введенными данными и допустимый начальный базис
| | В150 | В240 | В330 | В420 | В510 |
| А110 | 10 | - | - | - | - |
| А220 | 20 | - | - | - | - |
| А330 | 20 | 10 | - | - | - |
| А440 | - | 30 | 10 | - | - |
| А550 | - | - | 20 | 20 | 10 |
4. ИНСТРУКЦИЯ ДЛЯ ПОЛЬЗОВАТЕЛЯ
Общие сведения:
Программа производит вычисления допустимого начального базиса
Задача является сбалансированной. Поиск начального базиса происходит методом «северо-западного угла»
Управление:
Данные вводятся с клавиатуры:
Пользователь вводит запасы i-го потребителя. После нажатия клавиши «0» пользователь вводит запросы j-го поставщика. Далее на экране после нажатия клавиши «Enter» появляется таблица с вводимыми данными и начальный базис.
5. ИНСТРУКЦИЯ ДЛЯ ПРОГРАММИСТА
Данная программа реализуется с помощью процедурного языка TurboPascal 7.0, используется текстовый режим.
5.1 ТРЕБУЕМЫЕ ИНФОРМАЦИОННО–ВЫЧИСЛИТЕЛЬНЫЕ СРЕДСТВА:
1) техническое обеспечение: IBMPC\XT совместимые машины
а) оперативная память – не менее 8Мб
б) свободное место на жестком диске – не менее 60Кб
в) центральный процессор – от Intel 8088 до семейства Pentium или совместимых с ним
2) информационные средства для нормального функционирования программы достаточно иметь информационную систему MSDOS
5.2 ТИПЫ ПЕРЕМЕННЫХ, ИСПОЛЬЗОВАННЫХ В ПРОГРАММЕ:
constn=20 (строки)
m=20 (столбцы)
a:array [1..n] of integer; {массивзапасов}
b:array [1..m] of integer; {массивпотребностей}
a1:array [1..n] of integer; {вспомогательный массив запасов}
b1:array [1..m] of integer; {вспомогательный массив потребностей}
c:array [1..n,1..m] of integer; {основной массив в который производится запись базисного решения}
i,j,k,x,y,s1,s2:integer;
5.3 ПРОЦЕДУРЫ
procedurevvod_klav;(ввод данных с клавиатуры)
begin
i:=1;
k:=0;
s1:=0;
while (k=0) and (i<n) do
begin
write('введите запaсы ',i,'-того поставщика: ');