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

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

Задача: в m малой пункта производства А1,А2,Аm имеется однородный груз в количестве а1,а2,аm. Этот груз необходимо доставить в n пунктов назначения(В1,В2,Вn) в количестве b1,b2,bn. Рассчитать стоимость перевозки единицы груза из пункта А в пункт В, стоимость обозначается Cij.

Составим общую таблицу перевозок.

		В1	В2	…	Вn
		b1	b2	…	bn
A1	a1	С11 Х11	С11 Х11		Сn Хn
A2	a2	С21 Х21	С11 Х11		Сn Хn
…	…
An	an	С31 Х31	С11 Х11		Сn Хn

В задаче составить план перевозок позволяющий вывезти все грузы за min стоимость. В зависимости от стоимости должна выполнятся следующая функция. через Xij обозначаем количество груза перевозимого из пунка А в В.

Математическая модель закрытой транспортной задачи это выполняется при следующих условиях 1<i<m Xij>0

Основные этапы решения транспортной задачи.

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

Пример: на складах А1,А2,А3 имеются запасы в количестве 94,400,110 тонн, потребители В1,В2,В3 должны получить продукцию в количестве 140,300,160 тонн. Найти такой вариант при котором сумма затрат на перевозку будет минимальна. Расходы на перевозку заданы матрицей . Для начала находим , . ai=bj.

		В1	В2	В3
		140	300	160
A1	90	2 90	5	2
A2	400	4	1 300	5 100
A3	140	3 50	6	8 60

90*2+300*1+100*5+50*3+60*8=1600 ед.

2этап. Проверка найденного решения на оптимальность. Если система опорного решения оптимально то этому решению соответствует m+n действительных чисел Ui и Vj. Которые удовлетворяют следующему условию: Ui +Vj=Cij- для занятых клеток. Ui+Vj-Cij<=0 для пустых клеток. Значения Ui и Vj называются потенциалами, значение потенциала Ui всегда =0, все остальные значения находятся по формуле если найдены решение для Ui и Vj меньше 0, то вы нашли правильное решение, если>0, то задача требует другого решения.

		В1	В2	В3	Ui
		140	300	160
A1	90	2 90	5	2	0
A2	400	4	1 300	5 100	-2
A3	140	3 50	6	8 60	1
Vj		2	3	7

3 этап. Переход от одного опорного решения к другому. Наличие положительной оценки свободной клетки говорит, что опорное решение не найдено. При этом нужно перераспределить грузы таким образом чтобы одна ячейка была пустая, а остальные занятые при этом сроится многоугольник с четными вершинами. Около свободной вершины ставится знак +, остальные знаки чередуются из отрицательных вершин выбирают минимальную и её значение прибавляют в вершинам с +, и отнимают от вершин с -.

90- + 30 60

=

30+ 60- 110 0

		В1	В2	В3	Ui
		140	300	160
A1	90	2 30	5	2 60	0
A2	400	4	1 300	5 100	3
A3	140	3 110	6	8	1
Vj		2	-2	2

0+(-2)-5=-7

3+2-4=1>0

1+(-2)-6=-7

1+2-8=-5

		В1	В2	В3	Ui
		140	300	160
A1	90	2 30	5	2 60	0
A2	400	4	1 300	5 100	3
A3	140	3 110	6	8	1
Vj		2	-2	2

30- 60 0 90

=

0+ 100- 30 70

		В1	В2	В3	Ui
		140	300	160
A1	90	2	5	2 90	0
A2	400	4 30	1 300	5 70	2
A3	140	3 110	6	8	1
Vj		1	-2	2

0+1-2=-1

0-2-5=-7

2-2-6=-6

2+2-8=-4

@(х)2=2*90+30*4+300*1+70*5+110*3=1280

@(х1)=1610

На строящейся магистральной линии требуется разместить 5 пунктов. Для их строительства на 3 базы А1,А2,А3 поступил груз в количестве 140,180,160. Этот груз следует привести в пункты В1,В2,В3,В4,В5 в количествах 60,70,120,130,100 единиц. Тарифы перевозок заданы матрицей. Определить стоимость перевозок.

		В1	В2	В3	В4	В5	Ui
		60	70	120	130	100
A1	140	2	3 10	4	2 130	3
A2	180	2 60	5	1 120	4	2
A3	160	4	2 60	3	2	1 100
Vj

0 10 0 130 0

60 0 120 0 0

0 60 0 0 100

@(x1)=10*2+130*2+50*2+120*1+10*2+70*2+90*1=750

		В1	В2	В3	В4	В5	Ui
		60	70	120	130	100
A1	140	2 10	3	4	2 130	3	0
A2	180	2 50	5	1 120	4	2 10	0
A3	160	4	2 70	3	2	1 90	-1
Vj		2	3	1	2	2

0+3-3=0

0+1-4=-3

-1

-2

-3

-1

Задача 3

			В1	В2	В3	В4	Ui
			90	180	310	130
A1	280		4 90	5 180	3 10	7	0
A2	175		7	6	2 175	9
A3	125		1	3	9 125	8
А4		130	2	4	5	6 130
Vj

A175 125 140

B 180 110 60 90

9 7 5 3

1 2 4 5

8 10 12 1

		В1	В2	В3	В4	Ui
		180	110	60	90
A1	175	9 5	7 110	5 60	3	0
A2	125	1 125	2	4	5	-8
A3	140	8 50	10	12	1 90	-1
Vj		9	7	5	2

180+110+60+90=440

175+125+140=440

0+2-3=-1

-8+7-2=-3

-8+5-4=-7

-1+7-10=-4

@(x)=5*9+110*7+60*5+125+50*8+90=1730

Задача 4

А 200 190 160=550

В 140 70 210 130=550

2 4 5 1

5 3 8 4

1 6 3 2

		В1	В2	В3	В4	Ui
		140	70	210	130
A1	200	2	4 70	5	1 130
A2	190	5	3	8 190	4
A3	160	1 140	6	3 20	2
Vj

0+9-5=3

0+(-5)-1=-6

-1+2-5=-4

-6+4-6=-8

@(x)=140*2+60*4+30+50*8+130*4+160*3=280+240+30+400+520+480=1950

Классификация ИС по признаку структурированности задач

Различают структурированные задачи- это задачи где известны все её элементы и взаимосвязи между ними. Данный тип задач выражается в форме математической модели имеющий точный алгоритм решения.

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

3 тип частично структурированный- это задачи в которых известно часть элементов и часть связей между ними.

В информационной системе используемые для решения частично структурированных задач подразделяется на 2 вида:

1. Создающие управленческие отчеты и ориентированные на обработку данных.

2. Разрабатывающие возможные альтернативные решения которые делятся на 2 вида. 1) модельная информационная система предоставляет пользователю математически, статистические, финансовые и другие модели.2) экспортные ИС обеспечивают выработку и оценку возможных альтернатив связанных с обработкой знаний.

Классификация ИС по функциональному признаку и уровням управления.

1. Производственная

2. Маркетодовая

3. Финансовая

4. Кадровая

Тип ИС зависит от того чьи интересы она обслуживает и на каком уровне управления.

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

ИС специалистов. Основной задачей является интеграция новых сведений с помощью обработки бумажных документов. Такие ИС можно разделить на 2 группы. 1) ИС офисной автоматизации. 2) ИС обработки знаний.

ИС для менеджеров среднего звена. Основной задачей сравнение текущих показателей и составление текущих отчетов. Также делятся на 2 группы . 1) управленческие. 2) система поддержки принятия решений. Данная сиситема определена для пользователя.

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

ИС в фирме. В любой фирме должно присутствовать несколько ИС которые должны присутствовать на разных уровнях управления.

Управленческие решения и развитие уровня управления

ИС учета и хранения сырья и материалов

ИС маркетинга и прродаж

ИС взаимодействия с поставщиками

ИС оперативного контроля за производством

1 По степени автоматизации бывают ручные.

2 автоматические

3 автоматизированные

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

Информационно решающие- это системы осуществляют все операции в переработки информации по определенному алгоритму которые в свою очередь делятся на 2 класса.1) Управляющие вырабатывают информацию на основе которой человек принимает решение. 2) советующие вырабатывают информацию которая принимается человеком сведениями.

Классификация по сфере применения. Бывают интегрированные используются для автоматизации всех функций фирмы от проектирования до сбыта продукции. 2) ИС организационного управления предназначены для автоматизации функций управленческого персонала.

ИС управления технологическими процессами. Служит для автоматизации функций производственного персонала.

ИС автоматизированного проектирования. Предназначены для автоматизации функций инженеров, конструкторов, архитекторов.1) Классификация по масштабу бывают одиночные реализуются как правило на одном компьютере может содержать несколько простых приложений связанных с общим информационным фондом ориентированная на работу одного пользователя. 2) групповые ИС. Ориентированы на коллективное использование и строятся на базе локальной вычислительной сети. При их разработки используются серверы баз данных.

3) корпоративные ИС ориентированы на крупную компанию и могут поддерживать территориально разнесенные узлы и сети. Используется архитектура клиент-сервер.

По сфере применения

ИС

Обработка транзакций системы поддержки принятия решений Инд. Справочная система Офисные ИС

Оперативная обработка оперативная аналитическая электронная докуметация Документированная ИС

Презентаций обработка географическая ИС Автоматизация делопр.

Пакетная обработка экспертные системы гипертекстовая ИС управление докумтооборота

Презентаций

По способу организации

1. Система на основе архитектуры файл-сервер.

2. Система на основе клиент-сервер.

3. Система на основе многоуровневой архитектуры.

4. Система на основе интернет технологий.

Требования предъявляемые ИС

1. Гибкость- это способность адаптации и дальнейшего развития, а также возможность приспособления ИС к новым условиям

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

3. Эффективность- система будет эффективной если с учетом ею выделенных ресурсов она позволяет решать возложенные на нее задачи в минимальные сроки.

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

Жизненный цикл ИС- жизненным циклом называется период с момента задумки ИС до момента вывода ее из эксплуатации.

ИС предприятия разрабатывается как некий проект .

Проект- это ограниченное по времени целенаправленное изменение отдельной системы с изначально четко определенными целями достижение которых определяет завершение проекта.

Можно выделить основные отличительные черты проекта:

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

2. Ограниченность конечных целей.

3. Ограниченность бюджета.

4. Ограниченность продолжительности.

5. Ограниченность требуемых ресурсов.

6. Новизна для предприятия.

7. Комплексность.

8. Правовое и информационное обеспечение.

В системном плане проект может быть представлен в виде черного ящика.

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