Logo GenDocs.ru

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


Загрузка...

Автоматизированное рабочее место диспетчера транспортной службы - файл курсач АИУС.doc


Автоматизированное рабочее место диспетчера транспортной службы
скачать (161.8 kb.)

Доступные файлы (1):

курсач АИУС.doc324kb.07.06.2010 07:14скачать

содержание
Загрузка...

курсач АИУС.doc

Реклама MarketGid:
Загрузка...

Содержание


Содержание 1

Введение 2

Постановка задачи 3

Модель транспортной задачи 4

Нахождение опорного плана методом аппроксимации Фогеля. 7

Реализация метода в программный код на JavaScript. 10

Тестирование 17

Заключение 20

Список использованной литературы 21

Введение


Линейное программирование (ЛП) - наука о методах исследования и нахождения экстремумов линейной функции, на неизвестные которой наложены линейные ограничения. То есть, задача линейного программирования, это нахождение минимального или максимального значения линейной функции с учётом системы из линейных уравнений-ограничений. Всё вместе это даёт математическую модель, какого-либо экономического процесса.

Типы задач линейного программирования:

• задачи об использовании ресурсов, сырья, планирования производства;

• задачи составления рациона

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

• Задачи о раскрое материалов

• Транспортные задачи

В данной курсовой работе будет рассмотрена и исследована транспортная задача.


^

Постановка задачи


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

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

^

Модель транспортной задачи


Задача о размещении (транспортная задача) – это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.

Транспортная задача-

Однородный груз сосредоточен у т поставщиков в объемах .

Данный груз необходимо доставить п потребителям в объемах .

Известны (i=1,2,…,m; j=1,2,…,n)- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны.

Исходные данные транспортной задачи записываются в таблице вида
Таблица 1





















































Переменными(неизвестными) транспортной задачи являются (i=1,…,m;i=1,2,…,n)- объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в матрице перевозок

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

(1.1)

i=1,2,…,m, (1.2)

j=1,2,…,n, (1.3)

i=1,2,…,m; j=1,2,…,n. (1.4)

Целевая функция задачи (1.1) выражает требования обеспечить минимум суммарных затрат на перевозку всех грузов. Первая группа из т уравнений (1.2) описывает тот факт, что запасы всех т поставщиков вывозятся полностью. Вторая группа из n уравнений (1.3) выражает требования полностью удовлетворить запросы всех n потребителей. Неравенства (1.4) являются условиями неотрицательности всех переменных задачи.

Таким образом, математическая формулировка транспортной задачи состоит в следующем: найти переменные задачи

i=1,2,…,m; j=1,2,…,n,

удовлетворяющее системе ограничений (1.2), (1.3), условиям неотрицательности (1.4) и обеспечивающее минимум целевой функции (1.1).

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

.

Такая задача называется задачей с правильным балансом, а ее модель- закрытой. Если же это неравенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель- открытой.

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

^

Нахождение опорного плана методом аппроксимации Фогеля.


Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

На каждом шаге метода Фогеля для каждой i-й строки вычисляются штрафы как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом .

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

Пример:

Исходные данные приведены в таблице (рис 1.).



Рис. 1 Исходные данные.

Решение. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке. Так в строке A2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце B4 равна 6-2=4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу B4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки A1 и столбца B4. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта B4. Поэтому исключим из рассмотрения столбец B4 и будем считать запасы пункта A1 равными 160-110=50.



Рис. 2 Решение.

После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и во второй дополнительной строке. Как видно из этой таблицы, наибольшая указанная разность соответствует строке A1. Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее с столбцом B3. Следовательно, заполняем эту клетку. Поместив в нее число 50, тем самым предполагаем, что запасы в пункте A1 полностью исчерпаны, а потребности в пункте B3 стали равными 190-50=140. Исключим из рассмотрения строку A1 и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки A3 и столбца B3, строки A3 и столбца B2, строки A2 и столбца B1, строки A2 и столбца B2. В результате получим опорный план:



При этом плане общая стоимость перевозок такова:

S=1*50+2*110+4*120+5*20+2*30+3*140=1330.
^

Реализация метода в программный код на JavaScript.


function tran(form) {

strok = 5;

stolb = 4;

summ = 0;

var c = [form.c1.value, form.c2.value, form.c3.value, form.c4.value, form.c5.value ] ;

var p = [form.p1.value, form.p2.value, form.p3.value , form.p4.value] ;

var s = [ [form.s11.value, form.s12.value, form.s13.value , form.s14.value],

[form.s21.value, form.s22.value, form.s23.value , form.s24.value],

[form.s31.value, form.s32.value, form.s33.value , form.s34.value],

[form.s41.value, form.s42.value, form.s43.value , form.s44.value],

[form.s51.value, form.s52.value, form.s53.value , form.s54.value]];

var z = [[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0]];

var x = [0, 0, 0, 0, 0];

var y = [0, 0, 0, 0];

var min_str = [111, 111, 111, 111, 111] ;

var razn_str = [111, 111, 111, 111, 111] ;

var min_stolb = [111, 111, 111, 111] ;

var razn_stolb = [111, 111, 111, 111] ;

function find_param()

{

<!--поиск минимумов в строках -->

for (i=0; i<strok; i++)

{

min_str[i]=111;

for (j=0; j<stolb; j++){

if (isNaN(s[i][j])==false)

{

if (parseInt(s[i][j])<=parseInt(min_str[i]))

{min_str[i]=parseInt(s[i][j]);

x[i]=j;

}

}

}

}

<!--поиск минимумов в столбцах -->

for (j=0; j<stolb; j++)

{

min_stolb[j]=111;

for (i=0; i<strok; i++){

if (isNaN(s[i][j])==false)

{

if (parseInt(s[i][j])<=parseInt(min_stolb[j]))

{min_stolb[j]=parseInt(s[i][j]);

y[j]=i;

}

}

}

}

<!--поиск разностей в строках -->

for (i=0; i<strok; i++)

{

razn_str[i]=111;

if (c[i]==0) {razn_str[i]=0; continue;}

for (j=0; j<stolb; j++){

if ((Math.abs(parseInt(s[i][j])-min_str[i])<parseInt(razn_str[i])) && (j!=x[i])) razn_str[i]=Math.abs(parseInt(s[i][j])-min_str[i]);

}

}

<!--поиск разностей в столбцах -->

for (j=0; j<stolb; j++)

{

razn_stolb[j]=111;

if (p[j]==0) {razn_stolb[j]=0; continue;}

for (i=0; i<strok; i++){

if ((Math.abs(parseInt(s[i][j])-min_stolb[j])<parseInt(razn_stolb[j])) && (i!=y[j]) && Math.abs(parseInt(s[i][j])-min_stolb[j])>0) razn_stolb[j]=Math.abs(parseInt(s[i][j])-min_stolb[j]);

}

}

return

}

t=30;

<!--цикл подсчета затрат и плана перевозок-->

while (t!=0)

{ t--;

find_param()

<!--поиск максимальной разности и нахождение её координат-->

if (Math.max.apply( Math, razn_str)>=Math.max.apply( Math, razn_stolb))

{ max_razn=Math.max.apply( Math, razn_str);

for (i=0; i<strok; i++) {

if (max_razn==parseInt(razn_str[i]) && (parseInt(p[x[i]])>0))

{

if (parseInt(p[x[i]])<parseInt(c[i]))

{

z[i].splice(x[i], 1, p[x[i]]);

c[i]=c[i]-p[x[i]];

summ=summ+p[x[i]]*s[i][x[i]];

p[x[i]]=0;

s[i].splice(x[i], 1, NaN);

break;

}

else

{ z[i].splice(x[i], 1, c[i]);

p[x[i]]=p[x[i]]-c[i];

summ=summ+c[i]*s[i][x[i]];

c[i] = 0;

s[i].splice(x[i], 1, NaN);

break;

}

}

}

}

else { max_razn=Math.max.apply( Math, razn_stolb);

for (j=0; j<stolb; j++)

{

if (max_razn==razn_stolb[j] && parseInt(p[j])!=0)

{

if (parseInt(p[j])<parseInt(c[y[j]]))

{ z[y[j]].splice(j, 1, p[j]);

c[y[j]]=c[y[j]]-p[j] ;

summ=summ+p[j]*s[y[j]][j];

p[j] = 0;

s[y[j]].splice(j, 1, NaN);

break;

}

else

{ z[y[j]].splice(j, 1, c[y[j]]);

p[j]= p[j] - c[y[j]];

summ=summ+c[y[j]]*s[y[j]][j];

c[y[j]] = 0;

s[y[j]].splice(j, 1, NaN);

break;

}

}

}

}

}

<!--последняя проверка-->

for (j=0; j<stolb; j++)

{

if (p[j]==0) {razn_stolb[j]=0; continue;}

else {

if (parseInt(p[j])<parseInt(c[y[j]]))

{ z[y[j]].splice(j, 1, p[j]);

c[y[j]]=c[y[j]]-p[j] ;

summ=summ+p[j]*s[y[j]][j];

p[j] = 0;

break;

}

else

{ z[y[j]].splice(j, 1, c[y[j]]);

p[j]= p[j] - c[y[j]];

summ=summ+c[y[j]]*s[y[j]][j];

c[y[j]] = 0;

break;

}

}

}

<!--Вывод на экран плана перевозок и затрат-->

form.summ.value = summ;

for (i=0; i<strok; i++)

{

for (j=0; j<stolb; j++)

{

m=i+1;

n=j+1;

document.getElementById("z"+m+n).value = z[i][j];

}

}

document.getElementById("summ").innerHTML=summ;

}




^


Рис. 3 Вид интерфейса в браузере.



Тестирование


Решение примера в Exсel, при помощи функции поиск решения:



Рис. 4.

Возьмем пример с большим количеством складов, открытая задача:



Рис. 5 Решение задачи.


Рис. 6 Решение задачи в Exсel.

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

Заключение


Несмотря на то, что не во всех случаях наша программа решает задачу оптимизации выбора распределения (транспортировки) продукции – идеально.

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

Во-вторых. Программа производит автоматизированный расчет. Т.е. быстро и легко.

В-третьих. Для работы программы необходимы минимальные системные требования, практически любой браузер. А для удобства её можно выложить в локальную сеть или Интернет и воспользоваться ею сможет любой, у кого будет доступ.
^

Список использованной литературы



1. Зайченко, Ю.П. Исследование операций: учебное пособие / Ю.П.Зайченко. – 2-е изд. – Киев: Вища школа, 1979. – 392 с.

2. Куцый, Н.Н. Математические методы системного анализа и теория принятия решений: пособие по курсовой работе / Н.Н. Куцый. – Иркутск: изд-во Иркутск гос. технич. ун-та, 2008. – 79 с.

3. Экономико-математические методы и прикладные модели. Финстатинформ М., 1997

4. Абчук В.А., Экономико-математические методы. Санкт-Петербург Союз,1999

5. Советов Б.Я, Яковлев С.А., Моделирование систем. Практикум. М. Высшая школа,1999

6. Замков О.О., Толстопятенко А.В., Черемных Ю.Н., Математические методы в экономике. М.ДИС, 1997.


Скачать файл (161.8 kb.)

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

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru