Математические модели задач транспортного типа

Структурная схема системы ПДС.

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

Символы aiA от ИС поступают в виде кодовых комбинаций, которые состоят из единичных элементов (посылок). Кодовая комбинация характеризуется основанием кода m и числом единичных элементов, составляющих кодовую комбина-

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

В технике ПДС наибольшее распространение получили коды с основанием 2. Такие коды часто называют двоичными, или бинарными. Основными причинами широкого использования двоичных кодов являются простота реализации, надежность элементов двоичной логики, малая чувствительность к действию внешних помех и т. д. Поэтому в дальнейшем во всех случаях (если это не будет оговорено особо) рассматриваются двоичные коды. Примером двоичного кода является Международный телеграфный код № 2 (МТК-2), в котором каждому переданному символу соответствует пятиэлементная кодовая комбинация.

Используя пятиэлементные комбинации, можно организовать передачу только 32 символов. Вспомним, что русский алфавит состоит из 32 букв, кроме того, имеются цифры и желательно обеспечить передачу латинских букв, знаков препинания и т. п. Поэтому в коде МТК-2 одна и та же пятиэлементная кодовая комбинация используется до 3 раз в зависимости от режима передачи, который определяется так называемым регистром. В коде МТК-2 три регистра: русский, латинский и цифровой. Прежде чем вести передачу конкретных знаков, передатчик сообщает приёмнику с помощью специального служебного знака тот регистр, в котором будет вестись последующая передача. Тогда в зависимости от регистра каждая пятиэлементная кодовая комбинация, поступившая от ИС, может иметь одно из трех значений. Так, комбинация 11101 в русском регистре означает букву Я, в цифровом — 1, в латинском — Q. Такой подход позволяет значительно расширить объем передаваемых символов при том же числе элементов в кодовой комбинации (в рассмотренном примере за счёт использования трех регистров число различных передаваемых символов возрастает примерно в 3 раза).

Набор символов, предусмотренный кодом МТК-2, является до­статочным для написания телеграмм, а в некоторых случаях даже для передачи данных. Как правило, для передачи данных требуется использовать больше символов. В связи с этим был разработан семиэлементный код МТК-5, рекомендованный МККТТ. Он получил название стандартного кода передачи данных (СКПД). Код имеет два регистра.

Коды МТК-2 и МТК-5 в технике ПДС называются первичными кодами.

Сообщение, поступающее от ИС, в ряде случаев содержит из­быточность. Последнее обусловлено тем, что символы aiA, составляющие сообщение, могут быть статистически связаны. Это позволяет часть сообщения не передавать, восстанавливая его на приёме по известной статистической связи. Так, кстати, поступают при передаче телеграмм, исключая из текста союзы, предлоги, знаки препинания, поскольку они легко восстанавливаются при чтении телеграммы на основании известных правил построения фраз и слов. Конечно, избыточность в принимаемой телеграмме позволяет легко исправить часть искаженных слов (правиль­но их прочитать). Однако избыточность приводит к тому, что за заданный промежуток времени будет передано меньше сообщений и, следовательно, менее эффективно будет использоваться канал ПДС. Задачу устранения избыточности на передаче в системе НДС выполняет кодер источника, а восстановление принятого сообщения — декодер источника. Часто кодер и декодер источника включают в состав ИС и ПС.

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

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

Различают синхронные и асинхронные дискретные каналы. В синхронных дискретных каналах — каждый единичный элемент вводится в строго определенные моменты времени. Эти каналы предназначены для передачи только изохронных сигналов. По асинхронному каналу можно передавать любые сигналы — изохронные, анизохронные. Поэтому такие каналы получили название прозрачных, или кодонезависимых. Синхронные каналы являются непрозрачными, или кодозависимыми.

Дискретный канал в совокупности с кодером и декодером канала (УЗО) называется расширенным (РДК). Если применительно к дискретному каналу рассматривается передача единичных элементов, принимающих значение “О” или “1” и алфавит “источника”, работающего на дискретный канал, можно считать равным 2, то применительно к РДК рассматривается передача кодовых комбинаций длиной п элементов и при использовании двоичного кода число возможных комбинаций равно 2ⁿ. Следовательно, алфавит “источника”, работающего на РДК, можно считать равным 2^п, отсюда и название “расширенный” (элемент алфавита называется символом.) Таким образом, символами являются “0” и “1” для двоичного дискретного канала и кодовые комбинации применительно к РДК. В современной литературе по теории кодирования чаще всего под термином символ принято понимать элемент кодовой комбинации, т. е. “0” или “1”.

В технике передачи данных РДК называют каналом передачи данных.

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

Пример 1.1. Рассчитаем скорости телеграфирования В и передачи информации R в дискретном канале. Длительность единичного элемента т_о= 10 мс, каждый информационный элемент несёт 1 бит информации и пусть на каждые семь информационных элементов приходится один проверочный.

Скорость телеграфирования В=1/₀ и, следовательно, B=1/0,01 = 100 Бод. Скорость передачи информации будет определяться числом информационных элементов, переданных в секунду, т. е. R = B*7/8= 100*7/8 = 87,5 бит/с.

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

Другой характеристикой дискретного канала является верность передачи единичных элементов. Она определяется через коэффициент ошибок по элементам Rош = n_ош/ N _пер)

т. е. отношением числа ошибочно принятых элементов п_ош к об­щему числу переданных N_nep за интервал анализа.

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

Транспортная задача (ТЗ) является важнейшей частной задачей ЛП, имеющей обширные приложения не только к проблемам транспорта. Она выделяется в ЛП определенностью экономической характеристики, особенностями экономической характеристики, особенностями математической модели, наличием специфических методов решения.

Простейшая формулировка транспортной задачи по критерию стоимости следующая:

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

Требуется спланировать перевозки (т.е. указать, сколько единиц груза должно быть отправлено от i-го поставщика j-му потребителю) так, чтобы:

1) весь груз из пуктов отправления был вывезен;

2) потребности каждого пункта потребления были полностью удовлетворены;

3) суммарные издержки перевозок были минимальными.

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

Здесь количество груза, перевозимого из i -го пункта отправления в j -тый пункт назначения, равно,,. Запас груза в i -м пункте отправления определяется величиной,, а в j -тый пункта в грузе,. Матрица называется матрицей тарифов (издержек или транспортных расходов). Планом транспортной задачи называется матрица перевозок.

Если в плане перевозок переменная, то это значение записывают в соответствующую клетку (i,j) и считают загруженной (занятой) или базисной, если же, то клетку (i,j), как правило, оставляют свободной.

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

(3.1)

Переменные должны удовлетворять ограничениям по запасам (3.2), по потребностям (3.3) и условиям неотрицательности (3.4). В математической записи это можно представить так:

, (3.2)

, (3.3)

,, (3.4)

Таким образом, среди множества решений системы ограничений (3.2)-(3.3) требуется найти такое неотрицательное решение, которое минимизирует целевую функцию (3.1). Полученная задача является задачей ЛП. Решение ТЗ проводится проводится с помощью общего приема последовательного улучшения плана, который реализован в симплексном методе.

Дата добавления: 2013-12-13