Курсовая работа по Программирование (другое) на тему Основных понятий системы 1С:Предприятие 8 и их назначение. Задача учета транспорта 12

ВВЕДЕНИЕ
Задачи, связанные с «транспортной проблемой» - транспортные задачи, математически формализованы уже давно. Прежде всего, Л. Канторович в 1939 году опубликовал первые результаты исследований в области организации и планирования производства. Затем этому вопросу было посвящено множество исследований, особенно во время Второй мировой войны. (Он использовался для определения того, как перебрасывать войска, расположенные на тренировочных базах в разных частях Соединенных Штатов, на поля сражений в Европе и Азии.) В этот период Ф. Хичкок [4] дает первую математическую формулировку транспортной модели.
Позднее Г. Данциг [3] сформулировал транспортную задачу как специальную задачу линейного программирования. В дальнейшем многие авторы внесли значительный научный вклад в разработку новых идей и методов для решения различных аспектов транспортной задачи. Сегодня базовые математические настройки этой задачи позволяют эффективно решать ряд сопутствующих вопросов, таких как проблемы распределения и планирования, а также динамической маршрутизации в телекоммуникационных сетях [1].
 
1.Теоретическая часть
1.1 Математическая формулировка транспортной задачи
В общем виде транспортная задача представляет собой математическую модель, которая определяет оптимальную программу транспортировки определенных количеств однородных товаров (источников). A1, ..., находящтхся в так называемых центрах спроса (источниках) B1,..., Bn. Основным критерием оптимизации является минимизация общих затрат на транспортировку товара, хотя в качестве критерия может быть принято сокращение других параметров (общего времени транспортировки товара, степени вовлеченности денежных средств, и т.д.). При этом предполагаем, что существует физическое разделение между источниками и центрами спроса, а также общее количество различных способов доставки товаров. Таким образом, транспортная задача имеет естественное сетевое представление, как показано на рис. 1.

Рисунок 1. Схема всех возможных маршрутов транспортировки однородного товара

Чтобы сформулировать общую математическую форму транспортной модели, вот некоторые из ее ключевых элементов:
• Доступное количество промышленных товаров (поставка).: a1,..., am.
• Потребности потребительских центров (спрос): b1,..., bn.
• Затраты на транспортировку единицы продукции из источника Ai в источник Bj. Обозначим эти затраты как cij, где i = 1,..., m, j = 1,..., n.
• Количество товаров, перевезенных из i-го пункта отправления в j-й пункт отправления. Обозначим их как xij.
Основной целью решения транспортной задачи является нахождение оптимальных значений xij, при которых общие затраты на транспортировку определяются так называемой транспортной функцией быть наименьшей.
(1)
Кроме того, следующие ограничивающие условия должны быть выполнены
(2)
Это означает, что общее предложение из каждого источника должно быть полностью распределено по местам спроса, в то время как спрос для каждого центра спроса должен быть полностью удовлетворен. Естественно, количество товаров, определяющее переменные xij, неотрицательно и неизвестно, например, оно имеет значение xij ≥ 0 для любых i = 1,..., m, j = 1,..., n.
Транспортная функция (1) наряду с вышеуказанными функциями ограничения (2) определяют так называемую общую (математическую) форму транспортной задачи (TP). Это специальная форма задачи линейного программирования (LP). Достижение минимальных транспортных затрат, описываемых транспортными функциями (1), можно интерпретировать как минимальную проблему в "классической" задаче LP. Однако сама специфика этой модели позволяет нам использовать ряд различных, упрощенных процедур для ее решения. Прежде всего, TP может быть отображен в наглядном виде с помощью так называемой стандартной транспортной матрицы, показанной на рисунке рисунок 2.

Рисунок 2. Стандартная транспортировочная матрица

Данная матрица часто используется для более удобного представления и эффективного решения конкретных задач. На основе вышеописанных моделей можно доказать следующее утверждение, которое характеризует необходимые и достаточные условия разрешимости ТП.
Теорема 1. Транспортная задача имеет решение тогда и только тогда, когда общее предложение равно общему спросу, т. е.
(3)
Доказательство предыдущей (и следующей) теоремы можно найти, например, в [1]. Задачи TP, в которых выполняется равенство (3), называются замкнутыми транспортными задачами. Это также справедливо.
Теорема 2. В замкнутом TP система уравнений (3) имеет m + n – 1 линейно независимых уравнений, т.е. матрица коэффициентов этой системы имеет ранг m + n − 1. Исходя из предыдущих теорем, можно сделать вывод, что любое решение и TP имеют одинаковое количество значений xij, ровно m + n − 1, которое будет отличаться от нуля. Будем называть это значение базовым значением, в отличие от других, неосновных значений, для которых оно допустимо xij = 0. Основной целью при решении TP является нахождение оптимальных значений xij, обеспечивающих минимальные суммарные затраты на транспортировку грузов, т.е. значений, при которых транспортные функции (1) достигают своего минимума.
1.2. Программная реализация транспортной задачи. Определение исходного базового решения
Процесс определения оптимальных значений xij обычно выполняется в два этапа:
1. Определение исходного решения TP.
2. Преобразование исходного решения в оптимальное решение, т.е. программу транспортировки с минимальными общими затратами.
Таким образом, могут существовать различные способы определения исходного и оптимального решения. В следующем разделе будут более подробно описаны некоторые из них.
Формирование исходного базового решения является начальной процедурой размещения указанного количества товаров, которое будет удовлетворять заданным условиям ТП, главным образом системе ограничений (2). Основная цель состоит в том, чтобы создать одно из возможных решений для ТЦО, т.е. общего количества товаров, распределяемых по отдельным конечным продуктам в соответствующие пункты назначения. В то же время необходимо обеспечить соответствие предлагаемых конечных продуктов и спроса в пункте назначения.
Первоначальное базовое решение транспортной проблемы может быть найдено различными способами. Здесь приводим некоторые из наиболее распространенных методов, а также их программную реализацию, где указываем на качество получаемых решений.
A. Метод северо-западного угла, также известный как диагональный метод, является одним из простейших методов нахождения исходного решения. Распределение товаров производится из верхнего левого угла матрицы перевозок, т.е. из полей с координатами (1, 1). Распределение товаров осуществляется таким образом, чтобы либо полностью исчерпать предложение конечных потребителей, либо спрос получателя. Затем, в зависимости от того, полностью ли удовлетворен спрос или предложение, заполняется следующее смежное поле. Базовая алгоритмическая этапы этой процедуры состоят из следующих элементов программирования:
Шаг 1: Введите количество источников (m) и количество адресатов (n).
Шаг 2: Введите значения ai, bj и cij, i = 1,..., m, j = 1,..., n.
Шаг 3: Для значений i = 1,2,...,m и j=1,2,...,n повторите следующие шаги.
Шаг 4: Если ai < bj, то xij = ai, иначе xij = bj.
Шаг 5: Если xij > 0, то T = T + cij * xij; ai = ai - xij; bj = bj - xij.
Шаг 6: Выведите значения T и xij соответственно.
Б. Метод минимальных затрат, как следует из его названия, основан на комплексном заполнении полей с помощью наименьшего коэффициента транспортных расходов cij.
Таким образом, на большинстве m+n−1 шагов изначально получается базовое решение, т.е. программа транспортировки, в которой каждое базовое значение xkl > 0 получается по соотношению
(4)
Полученное решение обычно имеет более низкие транспортные расходы по сравнению с решением, полученным в результате предыдущего, диагональный метод.
В. Приближенный метод К. Фогеля, также известный как метод наибольших различий, безусловно, является самым качественным, но и самым сложным методом определения начального значения базового решения. Его основная идея заключается в расчете потенциальных потерь, понесенных при использовании внутренней строки, т.е. столбца транспортной матрицы, вместо хотя бы одного коэффициента cij в базовом решении включают месторождения с более высокими транспортными расходами. Другими словами, для каждого источника и пункта назначения рассчитывается потенциальная (возможная) потеря как разница двух наименьших коэффициентов cij. Строка или столбец с наибольшей разницей имеют наибольшие потенциальные потери и заполняются первыми, начиная с элемента с наименьшим коэффициентом транспортных расходов. На каждом последующем шаге повторяем ту же процедуру и, таким образом, получаем
исходное базовое решение для TP. Так же , как и предыдущая, описанная выше процедура может быть это легко показать в виде алгоритмов, а соответствующую процедуру программирования реализовать и решить с помощью компьютера.