Меню
Поиск



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


Таблица 4

  

 

80

120

160

120

120

1

80

3

4

2

40

160

4

5

8

80

3

80

200

2

3

120

6

80

7

В оставшейся матрицы С наименьшей является стоимость , максимально возможная перевозка, которую можно осуществить от первого поставщика к четвертому потребителю, равна . В соответствующую летку таблицы записываем перевозку . Запасы первого поставщика исчерпаны, исключаем его из рассмотрения. В матрице С вычеркиваем первую строку. Запросы четвертого потребителя уменьшаем на 40

В оставшейся части матрицы С минимальная стоимость . Заполняем одну из двух клеток таблицы (2,4) или (3,2). Пусть в клетку (2,4) запишем . Запросы четвертого потребителя удовлетворены полностью, исключаем его из рассмотрения, вычеркиваем четвертый столбец в матрице С. Уменьшаем запасы второго поставщика

В оставшейся части матрицы С минимальная стоимость . Запишем в клетку таблицы (3,2) перевозку  Исключаем из рассмотрения второго потребителя, а из матрицы С второй столбец. Вычисляем

В оставшейся части матрицы С наименьшая стоимость  Запишем в клетку таблицы (3,3) перевозку Исключаем из рассмотрения третьего поставщика, а из матрицы С третью строку. Определяем .

В матрице С остался единственный элемент . Записываем в клетку таблицы (2,3) перевозку .

Проверяем правильность построения опорного решения. Число занятых клеток таблицы равно N=m+n-1=3+4-1=6. Применяя метод вычеркивания, проверяем линейную независимость векторов условий, соответствующих положительным координатам решения. Порядок вычеркивания показан на матрице Х:

 1 2 5 6

Решение является «вычеркиваемым» и, следовательно, опорным.

Переход от опорного решения к другому. В транспортной задаче переход от оного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок(осуществляется сдвиг по циклу). Перевозка «загружается» в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение.

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

Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком «+», а четные знаком «-». Такой цикл называется означенным.

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


1.2.3  МЕТОД ПОТЕНЦИАЛОВ

Широко распространенным методом решения транспортных задач является метод потенциалов.

Если допустимое решение , i=1,2,…,m; j=1,2,…n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков  i=1,2,…,m и потребителей  j=1,2,…,n, удовлетворяющее следующим образом:

Группа равенств (2.1) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных  i=1,2,…,m и  j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

Группа неравенств (2.2) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде:

 (2.3)

Числа  называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.

Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные.

Оценки для свободных клеток транспортной таблицы используются при улучшении опорного решения. Для этого находят клетку (l,k) таблицы, соответствующую . Если , то решение оптимальное. Если же , то для соответствующей клетки (l,k) строят цикл и улучшаю решение, перераспределяют груз

 по этому циклу.

Алгоритм решения транспортных задач методом потенциалов:

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

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

3.                 Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений:

которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам:

если известен потенциал , и

если известен потенциал

4.                 Проверить выполнения условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам

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

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

Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком «-», в которой достигается  остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным .

Далее перейти к пункту 3 данного алгоритма.


1.2.4  МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

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

Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. При этом нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку (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 PC\XT совместимые машины

а) оперативная память – не менее 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.


Страницы: 1, 2




Новости
Мои настройки

   рефераты скачать  Наверх  рефераты скачать  

© 2009 Все права защищены.