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

КАЛИНИНГРАДСКИЙ  ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ИНСТИТУТ ЭКОНОМИКИ И МЕНЕДЖМЕНТА

К о н т р о л ь н а я   р а б о т а 
 

по дисциплине: Математическое моделирование экономических систем 

на тему:                Задача об оптимальной перевозке грузов (транспортная задача).                                        Оптимизационные модели 

                                                                              работу выполнил студент(ка)

                                                                           гр. Астапович Максим Владимирович

                                                                                                                          

                                                                                       

Руководитель  работы

                                                                                        Ульянкин П.Н. 

                                                                                        Дата сдачи ______________

                     

Работа  защищена с оценкой

                                                   __________________ 

“____” _____________ 2012г. 
 
 
 
 

Калининград

2012г.

Общая характеристика транспортной задачи

Условие: 
Однородный груз сосредоточен у m поставщиков в объемах a₁, a₂, ... a_m. 
Данный груз необходимо доставить n потребителям в объемах b_1, b₂ ... b_n. 
Известны C_ij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю. 
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.

Исходные  данные транспортной задачи записываются в виде таблицы:

Исходные  данные задачи могут  быть представлены в  виде:

• вектора А=(a₁,a₂,...,a_m) запасов поставщиков
• вектора B=(b₁,b₂,...,b_n) запросов потребителей
• матрицы стоимостей:

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

Переменными (неизвестными) транспортной задачи являются x_ij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю. 
Эти переменные могут быть записаны в виде матрицы перевозок:

Так как произведение C_ij*X_ij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:

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

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

Вторая группа из n уравнений выражает требование удовлетворить  запросы всех n потребителей полностью  и имеет вид:

Учитывая условие  неотрицательности объемов перевозок математическая модель выглядит следующим образом:

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

Такая задача называется задачей с правильным балансом, а модель задачи закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а модель задачи — открытой.

Математическая  формулировка транспортной задачи такова: найти переменные задачи X=(x_ij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1)

Пример 

Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице 34.2

Решение: 
1. Вводим переменные задачи (матрицу перевозок): 
 
2. Записываем матрицу стоимостей: 

3. Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

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

4. Составим систему ограничений задачи. 
Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика: 
 
Это означает, что запасы поставщиков вывозятся полностью.

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

Необходимо также  учитывать, что перевозки не могут  быть отрицательными: 

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

Использование оптимизационных  моделей при принятии решений

 

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

     Экономическая суть методов оптимизации заключается в том, что, исходя из наличия определенных ресурсов, выбирается такой способ их использования (распределения), при котором обеспечивается максимум (или минимум) интересующего ЛПР показателя.

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

     Трудности, возникающие при решении задач  математического программирования, определяются, в частности:

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

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

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

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

     Отметим еще два типа задач математического  программирования, имеющих широкую распространенность в практике принятия управленческих решений.

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

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

     Решение задач динамического и стохастического  программирования, а также ряда других задач (например, параметрического программирования), выходит за рамки настоящего курса лекций.

Линейные  модели оптимизации  в управлении

     Сначала рассмотрим задачи линейной оптимизации (или оптимизационные задачи линейного  программирования), математические модели которых содержат лишь линейные зависимости  от переменных.

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

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

     Общая задача линейной оптимизации заключается  в нахождении максимума (минимума) линейной целевой функции

 

      ,      (2.1)

       ,      (2.2)

      ,       (2.3)

      .        (2.4)

 

     Функция называется целевой функцией, критерием оптимальности или линейной формой.

     Вектор  значений неизвестных  , удовлетворяющих условию задачи (2.1)-(2.4), называется допустимым решением или допустимым планом задачи линейной оптимизации. Совокупность всех допустимых планов называется множеством допустимых планов. Допустимое решение называется оптимальным, если оно обеспечивает максимальное (или, в зависимости от условий задачи, - минимальное) значение целевой функции.

     Решение задач линейной оптимизации может  быть получено без особых затруднений (естественно, при корректной формулировке проблемы). Классическим методом решения  задач данного типа является симплекс-метод. В случае лишь двух переменных успешно  может использоваться также графический метод решения, обладающий преимуществом наглядности. Очевидно, в случае применение графического метода невозможно.

     При решении ряда оптимизационных задач  требуется, чтобы значения неизвестных выражались в целых числах. Естественно, к задачам подобного типа относятся те, в которых требуется определить необходимые для принятия решений значения физически цельных объектов (машин, агрегатов различного типа, людей, транспортных единиц и т.д. и т.п.). Такие задачи относятся к задачам целочисленной оптимизации. Математическая модель задачи линейной целочисленной оптимизации также определяется формулами (2.1)-(2.4), но в данном случае налагается дополнительное требование целочисленности всех (или части) неизвестных. Если требование целочисленности распространяется лишь на часть неизвестных величин задачи, то такая задача называется частично целочисленной.