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

заносить в таблицу только в том случае, когда они попадают в клетку (i,j), подлежащую заполнению, т.е. в таблицу заносятся только базисные нули , остальные клетки с нулевыми перевозками остаются пустыми.

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

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

Пример 3:

Составить опорное решение методом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5 потребителей. данные записаны в таблице 6


Таблица 6

В1

50

В2

40

В3

30

В4

20

В5

10

А1

10






А2

20






А3

30






А4

40






А5

50







Решение:

Распределяем запасы первого поставщика. Так как его запасы меньше запросов первого потребителя , то в клетку (1,1) записываем перевозку и исключаем из рассмотрения первого поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя .

Распределяем запасы второго поставщика. Так как его запасы , меньше запросов первого потребителя , то записываем в клетку (2,1) перевозку и исключаем из рассмотрения второго поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя .

Распределяем запасы третьего поставщика . Так как его запасы больше запросов первого потребителя , то записываем в клетку (3,1) перевозку и исключаем из рассмотрения первого потребителя. Определяем оставшиеся неудовлетворенными запросы третьего поставщика .

Распределяем запасы третьего поставщика . Так как его запасы меньше запросов второго потребителя , то в клетку (3,2) записываем перевозку и исключаем из рассмотрения третьего поставщика. Определяем оставшиеся неудовлетворенными запросы второго потребителя .

Распределяем запасы четвертого поставщика . Так как его запасы больше запросов второго потребителя , то записываем в клетку (4,2) перевозку и исключаем из рассмотрения второго потребителя. Определяем оставшиеся неудовлетворенными запросы четвертого поставщика .

Распределяем запасы четвертого поставщика . Так как его запасы меньше запросов третьего потребителя , то в клетку (4,3) записываем перевозку и исключаем из рассмотрения четвертого поставщика. Определяем оставшиеся неудовлетворенными запросы третьего потребителя .

Распределяем запасы пятого поставщика. Так как его запасы больше запросов третьего потребителя , то в клетку (5,3) записываем перевозку и исключаем из рассмотрения третьего потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика.

Распределяем запасы пятого поставщика. Так как его запасы больше запросов четвертого потребителя , то в клетку (5,4) записываем перевозку и исключаем из рассмотрения четвертого потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика.

Распределяем запасы пятого поставщика. Так как его запасы равны запросам пятого потребителя , то в клетку (5,5) записываем перевозку и исключаем из рассмотрения пятого поставщика и пятого потребителя.

Ввиду того, что задача с правильным балансом, запасы всех поставщиков исчерпаны и запросы всех потребителей удовлетворены.

Результаты построения опорного решения приведены в таблице 7.


В1

50

В2

40

В3

30

В4

20

В5

10

А1

10

10


-


-


-


-


А2

20

20 - - - -

А3

30

20


10


-


-


-


А4

40

-


30


10


-


-


А5

50

- - 20 20 10

1.3 БЛОК-СХЕМА (АЛГОРИТМ РЕШЕНИЯ)



нет нет


да




Метод

северо-

- западного

угла


метод

потенциалов


2. ФОРМЫ ВХОДНОЙ ИНФОРМАЦИИ


Входные данные вводятся с клавиатуры

  • Запасы i-го поставщика

  • запросы j-го потребителя

В данном примере

  • запасы поставщиков(10; 20; 30; 40; 50)

  • запросы потребителей(50; 40; 30; 20; 10)

3. ФОРМЫ ВЫХОДНОЙ ИНФОРМАЦИИ


Информация выводится на экран в виде таблицы с введенными данными и допустимый начальный базис


В1

50

В2

40

В3

30

В4

20

В5

10

А1

10

10


-


-


-


-


А2

20

20 - - - -

А3

30

20


10


-


-


-


А4

40

-


30


10


-


-


А5

50

- - 20 20 10

4. ИНСТРУКЦИЯ ДЛЯ ПОЛЬЗОВАТЕЛЯ


Общие сведения:


Программа производит вычисления допустимого начального базиса

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


Управление:


Данные вводятся с клавиатуры:

Пользователь вводит запасы i-го потребителя. После нажатия клавиши «0» пользователь вводит запросы j-го поставщика. Далее на экране после нажатия клавиши «Enter» появляется таблица с вводимыми данными и начальный базис.

5. ИНСТРУКЦИЯ ДЛЯ ПРОГРАММИСТА


Данная программа реализуется с помощью процедурного языка Turbo Pascal 7.0, используется текстовый режим.


5.1 ТРЕБУЕМЫЕ ИНФОРМАЦИОННО–ВЫЧИСЛИТЕЛЬНЫЕ СРЕДСТВА:


  1. техническое обеспечение: IBM PCXT совместимые машины

а) оперативная память – не менее 8Мб

б) свободное место на жестком диске – не менее 60Кб

в) центральный процессор – от Intel 8088 до семейства Pentium или совместимых с ним

2) информационные средства для нормального функционирования программы достаточно иметь информационную систему MS DOS


5.2 ТИПЫ ПЕРЕМЕННЫХ, ИСПОЛЬЗОВАННЫХ В ПРОГРАММЕ:


const n=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 ПРОЦЕДУРЫ


procedure vvod_klav;(ввод данных с клавиатуры)

begin

i:=1;

k:=0;

s1:=0;

while (k=0) and (i<n) do

begin

write('введите запaсы ',i,'-того поставщика: ');

readln(a[i]);

if a[i]=0 then

begin

k:=1;

i:=i-1;

end

else

begin

a1[i]:=a[i];

s1:=s1+a1[i];

i:=i+1;

end;

end;

j:=1;

k:=0;

s2:=0;

textcolor(5);

while (k=0) and (j<m) do

begin

write('введите запрос ',j,'-того потребителя: ');

readln(b[j]);

if b[j]=0 then

begin

k:=1;

j:=j-1;

end

else

begin

b1[j]:=b[j];

s2:=s2+b1[j];

j:=j+1;

end;

end;

textcolor(yellow);

k:=0;

if s1<s2 then

begin

writeln('ошибка ввода, проверьте баланс');

readln;

halt;

end;

if (s2<s1) and (k=0) then

begin

writeln('ошибка ввода, проверьте баланс');

readln;

halt; end;

x:=i;

y:=j;

end;

ЗАКЛЮЧЕНИЕ


Мне была поставлена задача составить программу для расчета начального базиса сбалансированной транспортной задачи, где суммарные запасы поставщиков равны суммарным запросам потребителей.

Программа реализована на языке программирования Паскаль.

Все вводимые данные и начальный базис выводятся в виде таблицы.

В программе удобный и понятный пользовательский интерфейс. Для ввода данных используется клавиатура. Данные, выводимые программой, соответствуют тем, что получены при расчетах без использования компьютера. Таким образом, поставленная задача была выполнена.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


1 Общий курс высшей математики для экономистов. Учебник / под ред В.И. Ермакова.- М.: ИНФА – М. – 656 с. – (серия «высшее образование»).

2 Сборник задач и упражнений по высшей математике: математическое программирование: учебник пособие / А.В. Кузнецов, В.А. Сакович, Н.И. Холод и др; МН.: выш. ик., 2002. – 447с.:ил.

3 Т.Л. Партыкина, И.И. Попов Математические методы: учебник. – М.: ФОРУМ: ИНФА-М, 2005. – 464 с.: ил – (профессиональное образование)

4. И.Г. Семакин Основы программирования: учебник для сред. проф. Образования / И.Г. Семакин, А.П.Шестаков. – 2-е изд., стер,- М.: Издательский центр «Академия», 2003.-432 с.

5 Федосеев В.В. и др. Экономико-математические методы и прикладные модели: учебное пособие для ВУЗов. - М.: Юнити, 2002.

6 Коршунов Ю.М. математические основы кибернетики: учебное пособие для ВУЗов. – М.: Энергоатомиздат, 1987.

ПРИЛОЖЕНИЕ А


Листинг программы

program sev_zap;

uses crt; {подключение модуля "crt"}

const n=5; {количество строк}

m=5; {количество столбцов}

var 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;

{ввод с клавиатуры}

procedure vvod_klav;

begin

i:=1;

k:=0;

s1:=0;

while (k=0) and (i<n) do

begin

write('введите запaсы ',i,'-того поставщика: ');

readln(a[i]);

if a[i]=0 then

begin

k:=1;

i:=i-1;

end

else

begin

a1[i]:=a[i];

s1:=s1+a1[i];

i:=i+1;

end;

end;

j:=1;

k:=0;

s2:=0;

textcolor(5);

while (k=0) and (j<m) do

begin

write('введите запрос ',j,'-того потребителя: ');

readln(b[j]);

if b[j]=0 then

begin

k:=1;

j:=j-1;

end

else

begin

b1[j]:=b[j];

s2:=s2+b1[j];

j:=j+1;

end;

end;

textcolor(yellow);

k:=0;

if s1<s2 then

begin

writeln('ошибка ввода, проверьте баланс');

readln;

halt;

end;

if (s2<s1) and (k=0) then

begin

writeln('ошибка ввода, проверьте баланс');

readln;

halt;

end;

x:=i;

y:=j;

end;

begin

textcolor(white);

clrscr; {очистка экрана}

writeln(‘Построение начального базиса в сбалансированной транспортной задаче методом северо-западного угла’);

writeln;

writeln(‘Программу составил: Руднев Егор Николаевич’);

writeln;

vvod_klav; {процедура ввода с клавиатуры}

repeat

k:=0;

if (b[j]-a[i]<0) then

begin

c[i,j]:=b[j];

a[i]:=a[i]-b[j];

b[j]:=0;

j:=j-1;

k:=1;

end;

if (b[j]-a[i]>0) and (k=0) then

begin

c[i,j]:=a[i];

b[j]:=b[j]-a[i];

a[i]:=0;

i:=i-1;

k:=1;

end;

if (b[j]-a[i]=0) and (k=0) then

begin

c[i,j]:=a[i];

a[i]:=0;

b[j]:=0;

i:=i-1;

j:=j-1;

end;

if (i=0) or (j=0) then break;

until false;

{вывод на экран базисного решения}

clrscr;

textcolor(white);

for i:=1 to x do

begin

for j:=1 to y do

if j=y then write(c[i,j]:6,' │ ',a1[i])

else

write(c[i,j]:6);

writeln;

end;

write(' ');

for i:=1 to y*6-4 do

write(#196);

writeln('┘');

for j:=1 to y do

write(b1[j]:6);

readln;

end.

41


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: