Многоэтапная транспортная задача оптимального размещения и концентрации производства

Контрольные, курсовые работы по экономико-математическим методам и моделям(ЭМММ).

Ведение.

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

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

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

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

Простейшая формулировка транспортной задачи по критерию стоимости  следующая: в m пунктах отправления (А₁, ..., А_m) находится соответственно а_1, ..., а_m единиц однородного груза (ресурсы), который должен быть доставлен n потребителям (В₁, ..., В_n) в количествах b₁, ..., b_n единиц (потребности). Известны транспортные издержки C_ij перевозок единицы груза из i-гo пункта отправления в j-й пункт потребления.

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

      Данная  работа состоит из двух глав. В первой главе рассматривается общий случай математической постановки задачи оптимизации и методы оптимизации  транспортной задачи линейного программирования. Во второй главе приводится пример решения двухэтапной транспортной задачи двумя методами: метод сведения к классической форме задачи и метод раздельного прикрепления поставщиков. Так же во второй главе рассмотрена компьютерная реализация рассматриваемой задаче в Microsoft Excel.

    Цели курсовой  работы:

- показать, как разрабатываются математические модели двухэтапных транспортных задач линейного программирования;

- решить сформулированные  математические задачи на ЭВМ  с использованием пакетов прикладных  программ линейного программирования.

 

1. Теоретические  сведения.

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

Подобные методы широко применимы в производстве, транспорте, организации процессов, в обучении, руководстве персоналом и др. К  числу наиболее известных задач, решаемых этим методом, относятся задача о назначениях, транспортная задача и др.

                 Задача о назначениях и распределении  работ является частным случаем транспортной задачи, в которой приняты следующие допущения: число поставщиков m равно числу потребителей n; запасы каждого поставщика а_i = 1; заявки каждого потребителя b_j = 1; каждый поставщик может поставлять грузы только одному потребителю; каждый потребитель может получать грузы только от одного поставщика.       

         Если не учитывать направление  оптимизации целевой функции (max или min), что не влияет на аналитические зависимости, то модель транспортной задачи при принятых выше допущениях получает вид модели задачи о назначениях. Если сумма всех запасов А_i у поставщика равняется сумме всех заявок В_j потребителей, то такую транспортную задачу называют сбалансированной; если А не равно В, то задача является несбалансированной, и её математическая модель может иметь вид:

Знак неравенства в  ограничениях для запасов а_i, означает, что объем груза, вывозимый от любого i-го поставщика по заявкам всех потребителей, не может превышать имеющегося у него запаса, при этом часть запаса груза может остаться невывезенной. Аналогично знак неравенства в ограничениях для заявок b_j означает, что груз, получаемый j-м поставщиком, должен быть не меньше заявки, но превышение заявки при этом допускается.

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

• В каком смысле распределение средств должно быть наилучшим?
• Какой вклад дает каждый объект (субъект)  в целевую 
  функцию?

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

       В различных отраслях народного хозяйства (материально-техническое снабжение, торговля) грузы могут доставляться через промежуточные пункты. Допустим, имеется m ( ) пунктов производства, n ( ) пунктов потребления и р ( ) – промежуточных баз. Как в обычной транспортной задаче, обозначим через a_i и b_j соответственно объемы поставок и потребления. Пусть d_k – мощность k-ой базы, c_ik и c_kj – соответственно стоимость перевозки единицы продукции от поставщиков на базы и с баз к потребителям. Тогда модель задачи примет вид

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

;

 

;

;

 X_kj³0; X_ik³0.

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

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

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

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

Таблица. 1.

Потребители и их объемы
Поставщики	Мощности	D1	….	Dp	B1	….	Bn
		d1	….	dp	b1	….	bn
A1	a1	I			II
…	…
Am	am
D1	D1	III			IV
…	…
Dp	dp

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Практическая  часть.

Многоэтапная  транспортная задача оптимального размещения и концентрации производства.

        Транспортная система состоит из пяти пунктов производства, шести пунктов промежуточной переработки и шести пунктов потребления. Известны объемы производства каждого из пунктов Ai (1 тыс. ед. товаров), пропускные способности пунктов промежуточной переработки Dk(1 тыс. ед. товаров), а так же потребности по потребителям Bj (1 тыс. ед. товаров). Известна стоимость доставки 1 тыс. ед. товаров на склад и доставки 1 тыс. ед. товара со склада потребителю. Эти данные представлены в таблицах.

Таблица 1.

Поставки  от производителей А1-А5 на склады D1-D6 и стоимость доставки партии товара на склад (тысячи денежных единиц).

	D1=100	D2 = 30	D3 =70	D4 =240	D5 =160	D6 =200
A1 = 120	3	5	1	4	2	3
A2 = 80	5	6	4	1	8	3
A3 = 300	3	1	5	2	1	3
A4 = 250	6	1	4	3	5	2
A5 = 50	1	3	5	2	8	4

Таблица 2.

Поставки  со складов потребителям и стоимость доставки партии товара со склада потребителям (тысячи денежных единиц).

	B1 = 40	B2 =160	B3 =120	B4 =150	B5 =130	B6 =200
D1 =100	9	3	4	1	5	2
D2 =30	1	6	2	5	3	8
D3=70	3	5	2	1	3	4
D4 =240	7	2	5	1	4	6
D5 =160	2	3	1	4	2	8
D6 =200	5	3	2	4	1	3