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

Размещено на http://www.allbest.ru/

Ведение

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

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

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

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

Простейшая формулировка транспортной задачи по критерию стоимости следующая: в 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_kj0; X_ik0.

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

Двухэтапную транспортную задачу легко свести к классической транспортной задаче. Для этого базы будем считать одновременно поставщиками и потребителями. Для каждой базы в расширенной матрице (поставщики + базы) -- (потребители + базы) отведем строку и столбец. Тогда матрица тарифов будет состоять из четырех блоков (табл. 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

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

1. Решить двухэтапную транспортную задачу

составить математическую модель

изобразить задачу графически

решить задачу методом потенциалов.

2. Решить эту же задачу путем раздельного прикрепления поставщиков к складам и складов к потребителям

составить математическую модель

изобразить задачу графически

решить задачу методом потенциалов.

Сравнить полученные результаты и сделать выводы.

Решить двухэтапные транспортные задачи с учетом дополнительных ограничений:

Из А1 в Д1 можно перевезти не менее 80 единиц груза,

Из А3 в Д4 перевозки не осуществляются и из Д4 в В2 перевозки так же запрещены,

Из Д6 в В5 можно перевезти не более 50 единиц груза.

Оценить и проанализировать раздельное влияние этих ограничений и общее их влияние на затраты.

5. Решить задачи п.1, п.2 и п. 4 (4 задачи) с использованием ЭВМ.

Решим двухэтапную транспортную задачу.

Обозначим через X_ik - количество продукции, поставляемое от i-го пункта производства на к-й промежуточный пункт (i=1, 2, 3, 4, 5; k= 1, 2, 3, 4, 5, 6), а через X_kj - количество продукции, поставляемое с к-го промежуточного пункта j-му потребителю (k= 1, 2, 3, 4, 5, 6; j=1, 2, 3,4, 5, 6). Тогда целевая функция, характеризующая суммарные транспортные расходы, запишется в виде:

Ограничения запишутся в виде:

120,

80,

300,

250,

50.

100,

30,

70,

240,

160,

200.

100,

30,

70,

240,

160,

200.

40,

160,

120,

150.

130

200.

Размещено на http://www.allbest.ru/

Условия положительности переменных:

X_ik0 (i=1, 2, 3, 4, 5; k= 1, 2, 3, 4, 5, 6); X_kj0 (k= 1, 2, 3, 4, 5, 6; j=1, 2, 3,4, 5, 6).

Так как 800, то можно решать двухэтапную транспортную задачу. Определяем число заполненных клеток первоначального опорного плана: 11 + 12 - 1 = 22.

Составляем начальный опорный план методом минимального элемента. Вначале заполняем первый или четвертый квадрант, затем третий, а затем оставшийся (первый или четвертый). В таблице 2.1 получен первоначальный опорный план. Проверим полученный план на оптимальность, для этого находим потенциалы U_i и V_j.

После того как мы определили потенциалы U_i и V_j, находим оценки свободных клеток:

S₈₃ = 0 - (1+0) = -1; S_{8 10} = 1 - (1+2) = -2; и так далее.

Полученный опорный план не оптимален, так как имеются отрицательные оценки, наибольшая по модулю из них S_{8 10}. Строим для заданной клетки замкнутый контур и улучшаем, полученный опорный план.

В результате получаем таблицу 2.2.

После того как мы определили потенциалы U_i и V_j, находим оценки свободных клеток:

S₈₃ = 0 - (1+0) = -1; S_{8 12} = 4 - (4+1) = -1; и так далее.

Полученный опорный план не оптимален, так как имеются отрицательные оценки, наибольшая по модулю из них S₈₃ и S_{8 12}. Строим для клетки S_{8 12} замкнутый контур и улучшаем, полученный опорный план.

В результате получаем таблицу 2.3.

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

f= (50•3 + 70•1 + 80•1 + 140•2 + 160•1 + 30•1+ 20•3 + 200•2 + 50•1) + (100•2 + 30•1 + 70•1 + 160•2 + 80•1+ 10•2 + 120•1 + 30•2 + 100•1 + 100•3) = 1280 + 1300 = 2580 ден. ед.

Решим задачу путем раздельного прикрепления поставщиков к складам и складов к потребителям.

Запишем начальные условия первого этапа задачи в форме табл. 2.3.

Таблица 2.4

Мощности поставщиков Аi	Промежуточные пункты и их спрос Dk
	D1 (100)	D2 (30)	D3 (70)	D4 (240)	D5 (160)	D6 (200)
А1 (120)	3 X11	5 X12	1 X13	4 X14	2 X15	3 X16
А2 (80)	5 X21	6 X22	4 X23	1 X24	8 X25	3 X26
А3 (300)	3 X31	1 X32	5 X33	2 X34	1 X35	3 X36
А4 (250)	6 X41	1 X42	4 X43	3 X44	5 X45	2 X46
А5 (50)	1 X51	3 X52	5 X53	2 X54	8 X55	4 X56

Составим математическую модель задачи.

Обозначим через Хik (i = 1,5; k = 1,6) объем продукции, который планируется перевезти от поставщика А_i, в промежуточный пункт D_k, а через f₁ - общие затраты на первом этапе транспортировки.

Целевая функция задачи запишется в виде:

f₁=3* X₁₁ + 5 * X₁₂ +...+ 4*X₅₆ (min) (2.2.1)

Сравнивая суммарную мощность поставщиков 120 + 80 + 300 + 250 + 50 = 800 со спросом на промежуточных пунктах 100 + 30 + 70 + 240 + 160 + 200 = 800, видим, что эти суммы совпадают. Следовательно, данная транспортная задача обладает закрытой моделью.

Переходя к ограничениям на переменные Х_ik, следует учесть, что спрос на промежуточных пунктах D_k, не может превышать мощности поставщиков, т.е.

X₁₁ + X₁₂ + X₁₃ + X₁₄ + X₁₅ + X₁₆ =120

X₂₁ + X₂₂ + X₂₃ + X₂₄ + X₂₅ + X₂₆ = 80 (2.2.2)

X₃₁ + X₃₂+ X₃₃ + X₃₄+ X₃₅ + X₃₆ = 300

X₄₁ + X₄₂+ X₄₃ + X₄₄+ X₄₅ + X₄₆ = 250

X₅₁ + X₅₂+ X₅₃ + X₅₄+ X₅₅ + X₅₆ = 50

Условия удовлетворения спроса на промежуточных пунктах D_k:

X₁₁ + X₂₁ + X₃₁+ X₄₁+ X₅₁ = 100

X₁₂ + X₂₂ + X₃₂ + X₄₂+ X₅₂ = 30

X₁₃ + X₂₃+ X₃₃+ X₄₃+ X₅₃ =70

X₁₄ + X₂₄+ X₃₄+ X₄₄ + X₅₄ = 240 (2.2.3)

X₁₅ + X₂₅+ X₃₅+ X₄₅ + X₅₅ = 160

X₁₆ + X₂₆+ X₃₆+ X₄₆ + X₅₆ = 200

Условия неотрицательности переменных:

Х_ij ?0 (i=1,5; k=1,6) (2.2.4)

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

Решим полученную задачу методом потенциалов.

Таблица 2.5

	D1 (100)	D2 (30)	D3 (70)	D4 (240)	D5 (160)	D6 (200)	Ui
А1 (120)	3 50	5	1 70	4	2 0	3	0
А2 (80)	5	6	4	1 80	8	3	-2
А3 (300)	3	1	5	2 140	1 160	3	-1
А4 (250)	6	1 30	4	3 20	5	2 200	0
А5 (50)	1 50	3	5	2	8	4	-2
Vj	3	1	1	3	2	2

Приступая к составлению исходного опорного плана, устанавливаем, что в нашем случае любой опорный план должен «загружать» m+n-1= 5+6-1=10 клеток.

Построим исходный опорный план методом минимального элемента.

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

U₁ + V₁ = 3

U₁ + V₃ = 1

U₁ + V₅ = 2

U₂ + V₄ =1

U₃ + V₄ =2

U₃ + V₅ = 1

U₄ + V₂ = 1

U₄ + V₄ = 3

U₄ + V₆ = 2

U₅ + V₁ = 1

составленных по заполненным клеткам. Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значение, например, U₄ = 0. Тогда остальные неизвестные находятся из системы.

Получаем

U₁ = 0, U₂ = -2, U₃ = -1, U₄ = 0, U₅ = -2, V₁ = 3, V₂ = 1, V₃ = 1, V₄ = 3, V₅ = 2, V₆ = 2.

Теперь можно найти оценки свободных клеток:

Д₁₂ = C₁₂ - (U₁ + V₂) = 5-(1 + 0)= 4, Д₁₄= 1, Д₁₆ = 1, Д₂₁ = 4, Д₂₂ = 7, Д₂₃ = 5, Д₂₅ = 8, Д₂₆= 3, Д₃₁= 1, Д₃₂= 1, Д₃₃ = 5, Д₃₆= 2 и т. Д.

Поскольку в табл. 2.5 свободных клеток с отрицательными оценками нет, то опорный план является оптимальным. Итак, получен оптимальный план:



	50	0	70	0	0	0
	0	0	0	80	0	0
X*=	0	0	0	140	160	0
	0	30	0	20	0	200
	50	0	0	0	0	0

Этому плану соответствуют минимальные суммарные затраты в 1280 ден. ед.

(f₁= 50•3 + 70•1 + 80•1 + 140•2 + 160•1 + 30•1+ 20•3 + 200•2 + 50•1 = 1280)

Запишем начальные условия второго этапа задачи в форме таблицы 2.6.

Таблица 2.6

Возможности промежуточных пунктов Dk	Пункты потребления и их спрос Вj
	В1 (40)	В2 (160)	В3 (120)	В4 (150)	В5 (130)	В6 (200)
D1 (100)	9 X11	3 X12	4 X13	1 X14	5 X15	2 X16
D2 (30)	1 X21	6 X22	2 X23	5 X24	3 X25	8 X26
D3 (70)	3 X31	5 X32	2 X33	1 X34	3 X35	4 X36
D4 (240)	7 X41	2 X42	5 X43	1 X44	4 X45	6 X46
D5 (160)	2 X51	3 X52	1 X53	4 X54	2 X55	8 X56
D6 (200)	5 X61	3 X62	2 X63	4 X64	1 X65	3 X66

Обозначим через Х_kj (k = 1,6; j = 1,6) объем продукции, который планируется перевезти из промежуточного пункта D_k к потребителю b_j, а через f₂ - общие затраты на втором этапе транспортировки.

Целевая функция задачи запишется в виде:

f₂ =9* X₁₁ + 3 * X₁₂ +...+ 3*X₆₆ (min) (2.2.5)

Сравнивая суммарные возможности промежуточных пунктов 100 + 30 + 70 + 240 + 160 + 200 = 800 со спросом потребителей 40 + 160 + 120 + 150 + 130 + 200 = 800, видим, что эти суммы совпадают. Следовательно, данная транспортная задача обладает закрытой моделью.

Переходя к ограничениям на переменные Х_kj, следует учесть, что спрос потребителей В_j, не может превышать возможности промежуточных пунктов, т.е.

X₁₁ + X₁₂ + X₁₃ + X₁₄ + X₁₅ + X₁₆ =100

X₂₁ + X₂₂ + X₂₃ + X₂₄ + X₂₅ + X₂₆ = 30 (2.2.6)

X₃₁ + X₃₂+ X₃₃ + X₃₄+ X₃₅ + X₃₆ = 70

X₄₁ + X₄₂+ X₄₃ + X₄₄+ X₄₅ + X₄₆ = 240

X₅₁ + X₅₂+ X₅₃ + X₅₄+ X₅₅ + X₅₆ = 160

X₆₁ + X₆₂+ X₆₃ + X₆₄+ X₆₅ + X₆₆ = 200

Условия удовлетворения спроса поставщиков Вj:

X₁₁ + X₂₁ + X₃₁+ X₄₁+ X₅₁ + X₆₁ = 40

X₁₂ + X₂₂ + X₃₂ + X₄₂+ X₅₂ + X₆₂ = 160

X₁₃ + X₂₃+ X₃₃ + X₄₃ + X₅₃ + X₆₃ = 120

X₁₄ + X₂₄+ X₃₄+ X₄₄ + X₅₄ + X₆₄ = 150 (2.2.7)

X₁₅ + X₂₅+ X₃₅+ X₄₅ + X₅₅ + X₆₅ = 130

X₁₆ + X₂₆+ X₃₆+ X₄₆ + X₅₆ + X₆₆ = 200

Условия неотрицательности переменных:

Х_ij ?0 (j=1,6; k=1,6) (2.2.8)

Соотношения (2.2.5) - (2.2.8) образуют экономико-математическую модель рассматриваемой задачи.

Таким образом, математическая модель задачи: целевая функция (2.2.5), описывающая суммарные затраты на втором этапе транспортировки, минимизируется при ограничениях (2.2.6) - (2.2.8).

Решим полученную транспортную задачу методом потенциалов.

Таблица 2.7

	В1 (40)	В2 (160)	В3 (120)	В4 (150)	В5 (130)	В6 (200)
D1 (100)	9	3	4	1	5	2 100	-2
D2 (30)	1 30	6	2	5	3	8	-1
D3 (70)	3	5	2	1 70	3	4 0	0
D4 (240)	7	2 160	5	1 80	4	6	0
D5 (160)	2 10	3	1 120	4	2 30	8	0
D6 (200)	5	3	2	4	1 100	3 100	-1
Vj	2	2	2	1	2	4

Приступая к составлению исходного опорного плана, устанавливаем, что в нашем случае любой опорный план должен «загружать» m+n-1= 6+6-1=11 клеток.

Построим исходный опорный план методом минимального элемента.

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

U₁ + V₆ = 2

U₂ + V₁ = 1

U₃ + V₄ = 1

U₃ + V₆ = 4

U₄ + V₂ = 2

U₄ + V₄ = 1

U₅ + V₁ = 2

U₅ + V₃ = 1

U₅ + V₅ = 2

U₆ + V₅ = 1

U₆ + V₆ = 3

Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значение, например, U₁ = 0. Тогда остальные неизвестные находятся из системы.

Получаем

U₁ = 0-2 U₂ = -1, U₃ = 0, U₄ = 0, U₅ = 0, U₆ = -1,V₁ = 2, V₂ = 2, V₃ = 2, V₄ = 1, V₅ = 2, V₆ = 4.

Теперь можно найти оценки свободных клеток: Д₁₁ = C₁₁ - (U₁ + V₁) = 9-(2-2)= 9 и так далее. Поскольку в таблице 2.8 свободных клеток с отрицательными оценками нет, то опорный план является оптимальным.

Итак, получен оптимальный план:



	0	0	0	0	0	100
	30	0	0	0	0	0
X*=	0	0	0	70	0	0
	0	160	0	80	0	0
	10	0	120	0	30	0
	0	0	0	0	100	100

Этому плану соответствуют минимальные суммарные затраты в 1300 ден. ед.

( f₂ = 100•2 + 30•1 + 70•1 + 160•2 + 80•1+ 10•2 + 120•1 + 30•2 + 100•1 + 100•3 = 1300)

Общие транспортные затраты в данном случае составят:

f = f₁ + f₂ = 1280 + 1300 = 2580 ден.ед.

Изобразим решение данной задачи на рисунке 2.2.

Сравнивая полученные результаты в пунктах 2.1 и 2.2, можем сделать вывод, что в нашем случае планы, полученные в пунктах 2.1 и 2.2 равнозначны. Так как суммарные транспортные затраты в обоих планах одинаковы и равны 2580 ден. ед.

Решим двухэтапные транспортные задачи с учетом дополнительных ограничений.

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

Z_min = (40•1 + 80•3 + 80•1 + 30•1 + 160•1 + 110•3+ 30•4 + 130•3 + 90•2 + 20•1 + 30•2) + (100•2 + 30•1 + 70•4 + 150•1 + 10•6+ 80•4 + 10•2 + 30•3 + 120•1 + 130•3+ 50•1+ 20•3) = 3420 тыс. ден. ед.

Можем сделать вывод, что введение дополнительных ограничений, привело к повышению значения целевой функции на 3420 - 2580 = 840 ден. ед.

Компьютерная реализация.

Решим задачу пункта 2.1 в среде Microsoft Excel, используя надстройку поиск решения.

Создадим математическую форму и введем исходные данные.

Заполним диалоговое окно поиск решения.

В результате получим:

Мы получили план перевозок c такими же суммарными затратами, что и в пункте 2.1. Следовательно, задача решена нами верно.

Решим задачу пункта 2.2 в среде Microsoft Excel, используя надстройку поиск решения.

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

В результате получим:

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

В результате получим:

Мы получили такое же решение, что и в пункте 2.2. Следовательно, в пункте 2.2 задача решена верно.

Решим двухэтапную транспортную задачу с учетом дополнительных ограничений:

Из А1 в Д1 можно перевезти не менее 80 единиц груза,

Из А3 в Д4 перевозки не осуществляются и из Д4 в В2 перевозки так же запрещены,

Из Д6 в В5 можно перевезти не более 50 единиц груза.

Используя форму задачи пункта 2.5.1, дополним в диалоговое окно поиск решения заданные три ограничения, получим:

Можем сделать вывод, что введение дополнительных ограничений, привело к повышению значения целевой функции на 3420 - 2580 = 840 ден. ед.

Заключение

Подводя итоги, проделанной нами работы, можем сделать вывод, что для рассматриваемого нами случая двухэтапной транспортной, когда возможности поставщиков равны потребностям потребителей, а вместимость промежуточных пунктов не превосходит по величине объем грузоперевозок, наиболее подходящим методом решения будет метод сведения двухэтапной транспортной задачи к классической задачи линейного программирования. Данный метод рассмотрен нами в пункте 2.1. главы 2. Значение целевой функции, полученное данным методом в нашем случае равно значению целевой функции, полученной в пункте 2.2. Обычно значение целевой функции, полученной при решении двухэтапной транспортной задачи выше значения целевой функции, полученной методом раздельного прикрепления. В нашем случае эти значения равны. Это объясняется тем, что данная задача имеет несколько оптимальных решений.

Анализируя влияние дополнительных ограничений, рассмотренное нами в пункте 2.4 главы 2, можем отметить, что при их введении значение целевой функции возрастает на 840 тыс. ден. ед.

Литература

1. Таха X. Введение в исследование операций. М: Издательский дом "Вильяме", 2001. 912 с.

2. Эддоус М., Стэнсфилд Р. Методы принятия решений. М.: Юнити, 1997. 590 с.

3. Кузнецов А.В., Сакович В.А., Холод II.И. Высшая математика: Математическое программирование. Мн.: Вышэйшая школа, 2001. 351 с.

4. Сборник задач и упражнений по высшей математике: Математическое программирование / Под общей ред. А.В. Кузнецова и Р.А. Рутковского. Мн.: Вышэйшая школа, 2002. 447 с.

5. Экономико-математические методы и модели / Под ред. А.В. Кузнецова. Мн.: БГЭУ, 1999. 413 с.

6. Исследование операций в экономике / Под ред. НЛП. Кремера. М.: Банки и биржи -Юнити, 1997. 407 с.

7. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Высшая школа, 2001. 208 с.

8. Смородинский С.С., Батин Н.В. Оптимизация решений на основе методов и моделей математического программирования. Мн.: БГУИР, 2003. 136 с.

9. Смородинский С.С., Батин Н.В. Методы анализа и принятия решений в слабоструктурированных задачах. Мн.: БГУИР, 2002. 116 с.

10. Смородинский С.С., Батин Н.В. Анализ и оптимизация систем на основе аналитических моделей. Мн.: БГУИР, 1997. 77 с.

Размещено на Allbest.ru

...