39

Содержание

Содержание 3

Введение 4

1Аналитическая часть 5

1.1Описание и постановка задачи 5

1.2Описание и анализ математической модели 7

1.3Обоснование выбора инструментальных средств 8

2Технологическая часть 9

2.1Назначение и цель создания 9

2.2Требования к системе 9

2.2.1Требования к функциям системы 9

2.2.2Требования к интерфейсу пользователя 9

2.2.3Требования к защите информации 10

2.3Перечень и описание входных данных 10

2.4Руководство к использованию 11

2.5Результаты экспериментальной проверки 12

3Охрана труда и техники безопасности 13

Заключение 16

Список используемой литературы. 17

Приложение А 18

Приложение В 22

Введение

Транспортная задача – это задача о наиболее экономичном плане перевозок груза. Транспортная задача является одной из самых распространенных специальных задач линейного программирования. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например, А.Н. Толстым.

Первая строгая постановка транспортной задачи принадлежит Хичкоку, и поэтому в зарубежной литературе иногда ее называют проблемой Хичкока.

Первый точный метод решения транспортной задачи разработан советскими учеными Л.В. Канторовичем и М.К. Гавуриным.

1. Аналитическая часть

1. Описание и постановка задачи

Пусть в пунктах А₁, А₂, …, А_m производят некоторый однородный продукт, причем объем производства в пункте А_i составляет a_i единиц (i = 1, 2, …, m). Допустим, что данный продукт потребляют в пунктах В₁, …, В_n, а объем потребления в пункте В_j составляет b_j единиц (j = 1, 2, …, n).

Предположим, что из каждого пункта производства возможна транспортировка продукта в любой пункт потребления. Транспортные издержки по перевозке из пункта А_i в пункт В_j единицы продукции равны c_ij (i = 1, 2, …, m; j = 1, 2, …, n).

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

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

Пусть x_ij – количество продукта, перевозимого из пункта А_i в пункт В_j. Требуется определить множество переменных x_ij>0 (i = 1, 2, …, m; j = 1, 2, …, n), удовлетворяющих условиям

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

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

и таких, что целевая функция

(1.3)

достигает минимума.

Таблица 1.1 – Табличная форма записи условий транспортной задачи

Пункты потребления Пункты производства	B1	B2	B3	…	Bn	Вj ai
A1	c11	c12	c13	…	c1n	a1
A2	c21	c22	c23	…	c2n	a2
…	…	…	…	…	…	…
Am	cm1	cm2	cm3	…	cmn	am
Аi bj	b1	b2	b3	…	bn	Объем производства Объем потребления

Условие (1.1) гарантирует полный вывоз продукта из всех пунктов производства, а условие (1.2) означает полное удовлетворение спроса во всех пунктах потребления.

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

В открытой форме эти суммы не равны.

Необходимым и достаточным условием разрешимости транспортной задачи является равенство:

Если , то вводят фиктивный (n+1) пункт назначения с потребностью и полагают .

Если , то вводят фиктивный (m+1) пункт назначения с запасами и полагают .