Общий вид транспортной матрицы задачи о назначениях

Транспортная задача и ее реализация

Транспортная задача является одной из наиболее распространенных задач линейного программирования и нахо­дит широкое практическое приложение.

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

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

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

Стоимость всего плана выразится двойной суммой

Систему ограничений получаем из следующих условий задачи:

1) все грузы должны быть перевезены, т.е.

;

2) все потребности должны быть удовлетворены, т.е.

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

при ограничениях

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

;

Транспортная задача, в которой суммарные запасы и потреб­ности совпадают, т.е. выполняется условие (4.20), называется за­крытой моделью; в противном случае – открытой.

Для открытой модели может быть два случая:

1) суммарные запасы превышают суммарные потребности :

2) суммарные потребности превышают суммарные запасы

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

Задача заключается в нахождении минимального значения линейной функции

при ограничениях в случае (1):

при ограничениях в случае (2):

Открытая модель решается приведением к закрытой модели. В случае (1), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель , потребность, которая описывается формулой:

Для случая (2), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик запа­сы которого описываются выражением:

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

Транспортная задача состоит из уравнений с неизвест­ными.

Матрицу перевозок , удовлетворяющую услови­ям (4.24)–(4.25), называют планом перевозок транспортной задачи, а – перевозками.

План , при котором целевая функция (4.23) обращается в минимум, называется оптимальным.

4.6. Применение транспортных моделей
к решению некоторых экономических задач

Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономичес­ких задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов имеют различный смысл в зависимости от конкретной экономической задачи.

К таким за­дачам относятся:

· оптимальное закрепление за станками операций по
обработке деталей. В них является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каж­дый из станков, чтобы обработать максимальное количество деталей;

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

· задача о сокращении производства с учетом суммарных рас­ходов на изготовление и транспортировку продукции;

Ресурсы	Работы	Количество ресурсов
...
Количество работ

Экономико-математическая модель задачи формулируется как

при ограничениях:

По сравнению с транспортной задачей процесс приведения задачи о назначениях к сбалансированному виду имеет свои осо­бенности (принимают значение «0» или «1»). При решении задач о назначении в Excel необходимо учиты­вать, что переменные являются булевыми.

5. Балансовые модели

Эффективное функционирование экономики пред­полагает наличие баланса между отдельными отраслями.

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

Для наглядного выражения взаимной связи между отраслями используют таблицы определен­ного вида, которые называют таблицами межотраслевого баланса. Впервые эти таблицы были опубликованы в 1926 г., в России.

Математическая модель межотраслевого баланса (МОБ), допуска­ющая широкие возможности анализа и прогноза, появилась позже (1936 г.) в трудах американского экономиста Василия Васильевича Леонтьева. В 1973 г. В.В. Леонтьев был удостоен премии Альфреда Нобеля по экономике за развитие и применение данных моделей.

Дата добавления: 2014-12-26; Просмотров: 1412; Нарушение авторских прав?; Мы поможем в написании вашей работы!