Решение задач линейного программирования

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

1. Задача планирования производства

Предприятию ООО «ТИТАН», одним из видов деятельности которого является выполнение токарных, фрезерных и сверлильных работ, поступил заказ на производство гаек стремянки, гаек штанги, гаек МОД и колец шкворня в количестве соответственно шт. Производство заказанной токарной продукции в полном объеме ограничено запасами имеющихся ресурсов (трудозатратами - чел.-час., запасом стали - кг, а также выделенными денежными средствами на оплату труда рабочих и последующую обработку токарной продукции - руб.). Кроме того, известно, что для производства единицы продукции каждого вида требуется соответственно кг стали, трудозатраты при этом составляют соответственно чел.-час. За каждую изготовленную деталь рабочий предприятия получает руб., последующая обработка единицы изделия каждого вида требует затрат денежных средств в размере руб. соответственно.

Задача оптимизации производства для ООО «ТИТАН» ставится в форме максимизации дополнительной прибыли предприятия при заданных ассортименте выпускаемой продукции и ограничениях на имеющиеся запасы ресурсов, при условии, что прибыль от реализации единицы продукции каждого вида составляет соответственно руб.

Исходные данные задачи представлены в таблице 1.

Необходимо: линейный задача транспорт производство

1. Построить экономико-математическую модель представленной задачи линейного программирования (с учетом условия целочисленности).

2. Определить с помощью надстройки «Поиск решения» в Microsoft Excel оптимальный план производства продукции ООО «ТИТАН» (количество гаек стремянки, гаек штанги, гаек МОД и колец шкворня).

3. Дать экономическую интерпретацию полученного решения. Сформулировать оптимальное управленческое решение в описанных условиях.

Таблица 1

Показатель	Ассортимент выпускаемой продукции
	Гайка стремянки	Гайка штанги	Гайка МОД	Кольцо шкворня
	2400	2500	2300	2100
	0,321	0,291	0,531	1,651
	0,234	0,249	0,514	0,299
	6,015	8,015	15,015	8,015
	5,985	4,985	6,985	7,985
	10	13	20	14
	2700
	3800
	51500

Решение.

1. Построим экономико-математическую модель представленной задачи линейного программирования (с учетом условия целочисленности).

Обозначим через (где ) - объём производства продукции ООО «ТИТАН» (количество гаек стремянки, гаек штанги, гаек МОД и колец шкворня).

Тогда дополнительная прибыль предприятия при заданном ассортименте выпускаемой продукции составит:

Ограничения по запасам имеющихся ресурсов:

Ограничения по объему производства:

Условия неотрицательности объемов производства:

Условия целочисленности объемов производства:

.

Экономико-математическая модель представленной задачи планирования производства составлена.

2. Определим с помощью надстройки «Поиск решения» в Microsoft Excel оптимальный план производства продукции ООО «ТИТАН» (количество гаек стремянки, гаек штанги, гаек МОД и колец шкворня).

Таблица 2. Результат поиска решения (оптимального плана производства)

Исходные данные задания 1
Токарная продукция ООО "ТИТАН"	гайка стремянки	гайка штанги	гайка МОД	кольцо шкворня
Прибыль от реализации единицы продукции каждого вида, руб.	10	13	20	14
Заказ на производство токарной продукции, шт.	2400	2500	2300	2100
Ресурсы	Затраты на производство единицы продукции каждого вида	Запасы имеющихся ресурсов	Требуемое количество ресурсов
	гайка стремянки	гайка штанги	гайка МОД	кольцо шкворня
Сталь, кг.	0,321	0,291	0,531	1,651	3800	1186,074
Трудозатраты, чел/час.	0,234	0,249	0,514	0,299	2700	1066,316
Оплата рабочему, руб.	6,015	8,015	15,015	8,015	51500	51498
Денежные затраты по последующую обработку изделия, руб.	5,985	4,985	6,985	7,985
Токарная продукция ООО "ТИТАН"	гайка стремянки	гайка штанги	гайка МОД	кольцо шкворня
	X1	X2	X3	X4
Оптимальный план производства	1	2500	863	0
Целевая функция (доп.доход "ТИТАН" от производства токарной продукции)	49 770р.

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

Для обеспечения максимальной дополнительной прибыли в размере 49770 рублей предприятию ООО «ТИТАН» следует производить гайки стремянки в количестве 1 шт., гайки штанги - 2500 шт., гайки МОД - 863 шт. и кольца шкворня - 0 шт. в месяц.

Дефицитным ресурсом при этом ничего не является, поскольку все остатки остаются. Увеличение недефицитных ресурсов: запас стали, трудозатраты, денежных средств на оплату труда рабочих и последующую обработку изделий, не может влиять на оптимальный план производства токарной продукции ООО «ТИТАН».

2. Транспортная задача

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

Перевозка угля от шахт до фабрик осуществляется с помощью железнодорожного транспорта. Транспортные затраты составляют руб. за т.-км. Расстояние от шахт до углеперерабатывающих фабрик приведено в следующей таблице 3:

Таблица 3.Расстояние от шахт до углеперерабатывающих фабрик, в км.

Угольные шахты	Углеперерабатывающие фабрики
	Расстояние от шахт до углеперерабатывающих фабрик, км
	24 26 50	17 41	44 15

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

Таблица 4. Исходные данные транспортной задачи

Показатель
Значение	250	190	170	90	260	210	230	650	44	28	39	36	19

Необходимо:

1. Построить экономико-математическую модель представленной транспортной задачи.

2. Определить с помощью надстройки «Поиск решения» в Microsoft Excel оптимальное распределение поставок угля с угольных шахт на перерабатывающие фабрики, при котором совокупные транспортные издержки будут минимальны.

3. Дать экономическую интерпретацию полученного решения. Сформулировать оптимальное управленческое решение в описанных условиях.

4. Найти с помощью надстройки «Поиск решения» в Microsoft Excel оптимальное распределение поставок угля с угольных шахт на перерабатывающие фабрики при условии, что в регионе открылась пятая угольная шахта с объемом добычи угля в тонн в день, расстояние от которой до перерабатывающих фабрик составляет соответственно () км. Дать экономическую интерпретацию полученного решения.

5. Найти с помощью надстройки «Поиск решения» в Microsoft Excel оптимальное распределение поставок угля с угольных шахт на перерабатывающие фабрики при условии, что открылась четвертая углеперерабатывающая фабрика с производственной мощностью в тонн в день, при этом расстояние от каждой шахты до новой фабрики составляет соответственно () км. Дать экономическую интерпретацию полученного решения.

Решение.

1. Построим экономико-математическую модель представленной транспортной задачи.

Обозначим через - объём перевозки угля от i-ой шахты до j-ой перерабатывающей фабрики.

Тогда суммарные транспортные затраты на перевозку составят:

Заданные объемы добычи угольных шахт и производственные возможности перерабатывающих фабрик накладывают ограничения на значения объемов перевозок угля :

Мощность всех шахт должна быть реализована:

Потребности фабрик должны быть удовлетворены:

Объемы перевозимого угля не могут быть отрицательными:

Экономико-математическая модель представленной транспортной задачи составлена.

2. Определим с помощью надстройки «Поиск решения» в Microsoft Excel оптимальное распределение поставок угля с угольных шахт на перерабатывающие фабрики, при котором совокупные транспортные издержки будут минимальны.

Для начала проверим тип представленной транспортной задачи. Так как

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

Таблица 5. Результат поиска решения (оптимального распределения поставок угля)

Угольные шахты	Углеперерабатывающие фабрики	Мощность угольных шахт
	В1	В2	В3
	Расстояние от шахт до углеперерабатывающих фабрик, км
А1	24	28	44	250
А2	44	17	36	190
А3	26	39	15	170
А4	50	41	19	90
Производственные возможности фабрик	260	210	230
Матрица оптимального распределения поставок угля	В1	В2	В3	Вывезенное из шахт количество угля
А1	230	20	0	250
А2	0	190	0	190
А3	30	0	140	170
А4	0	0	90	90
Поступившие на фабрику количество угля	260	210	230
Целевая функция (суммарные транспортные затраты на перевозку угля)	9 035 000р.

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

Итак, для того, чтобы совокупные транспортные издержки на перевозку угля от шахт до перерабатывающих фабрик, осуществляющуюся с помощью железнодорожного транспорта, были минимальны и составили 9 035 тыс.руб. необходимо придерживаться следующего оптимального плана распределения поставок угля:

- с первой шахты 230 т. добытого за день угля необходимо перевезти на первую перерабатывающую фабрику, 20 т. - на вторую;

- со второй шахты весь объем добытого за день угля (это 190 т.) необходимо перевезти на вторую перерабатывающую фабрику;

- с третьей шахты 30 т. необходимо перевезти на первую перерабатывающую фабрику и 140 т. - на третью;

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

4. Найдем с помощью надстройки «Поиск решения» в Microsoft Excel оптимальное распределение поставок угля с угольных шахт на перерабатывающие фабрики при условии, что в регионе открылась пятая угольная шахта с объемом добычи угля в тонн в день, расстояние от которой до перерабатывающих фабрик составляет соответственно () км.

Дополнительные исходные данные транспортной задачи представлены в таблице 6:

Таблица 6

Показатель
Значение	280	22	26	28

Сначала составим экономико-математическую модель представленной транспортной задачи с измененными условиями:

Мощность всех шахт должна быть реализована:

Потребности фабрик должны быть удовлетворены:

Объем перевозимого угля не могут быть отрицательными:

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

Так как

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

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

.

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

После введения фиктивной фабрики задача становится закрытой, и её математическая модель будет иметь вид:

Мощность всех шахт должна быть реализована:

Потребности фабрик должны быть удовлетворены:

Объем перевозимого угля не могут быть отрицательными:

Таблица 7. Результат поиска решения (оптимального распределения поставок в задаче с измененными условиями)

Транспортные затраты за 1 т.-км.:	650	руб
Угольные шахты	Углеперерабатывающие фабрики	Мощность угольных шахт
	В1	В2	В3	В4 (фиктивная)
	Расстояние от шахт до углеперерабатывающих фабрик, км
А1	24	28	44	0	250
А2	44	17	36	0	190
А3	26	39	15	0	170
А4	50	41	19	0	90
А5	22	26	28	0	280
Производственные возможности фабрик	260	210	230	280
Матрица оптимального распределения поставок угля	В1	В2	В3	В4 (фиктивная)	Вывезенное из шахт количество угля
А1	0	0	0	250	250
А2	0	160	0	30	190
А3	120	50	0	0	170
А4	0	0	90	0	90
А5	140	0	140	0	280
Поступившие на фабрику количество угля	260	210	230	280
Целевая функция (суммарные транспортные затраты на перевозку угля)	10 725 000р.

Дадим экономическую интерпретацию полученного решения.

Итак, для того, чтобы совокупные транспортные издержки на перевозку угля от шахт до перерабатывающих фабрик, осуществляющуюся с помощью железнодорожного транспорта, были минимальны и составили 10 725 тыс.руб. необходимо придерживаться следующего оптимального плана распределения поставок угля:

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

- со второй шахты 160 т. необходимо перевезти на вторую перерабатывающую фабрику и 30 т. - на четвертую;

- с третьей шахты 120 т. необходимо перевезти на первую перерабатывающую фабрику и 50 т. - на вторую;

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

- с пятой шахты 140 т. необходимо перевезти на первую перерабатывающую фабрику и 140 т. - на третью.

5. Найдем с помощью надстройки «Поиск решения» в Microsoft Excel оптимальное распределение поставок угля с угольных шахт на перерабатывающие фабрики при условии, что открылась четвертая углеперерабатывающая фабрика с производственной мощностью в тонн в день, при этом расстояние от каждой шахты до новой фабрики составляет соответственно () км.

Дополнительные исходные данные транспортной задачи представлены в таблице 8:

Таблица 8

Показатель
Значение	390	19	17	21	44

Сначала составим экономико-математическую модель представленной транспортной задачи с измененными условиями:

Мощность всех шахт должна быть реализована:

Потребности фабрик должны быть удовлетворены:

Объем перевозимого угля не могут быть отрицательными:

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

Так как

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

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

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

После введения фиктивной шахты задача становится закрытой, и её математическая модель будет иметь вид:

Мощность всех шахт должна быть реализована:

Потребности фабрик должны быть удовлетворены:

Объем перевозимого угля не могут быть отрицательными:

Таблица 9. Результат поиска решения (оптимального распределения поставок в задаче с измененными условиями)

Транспортные затраты за 1 т.-км.:	650	руб.
Угольные шахты	Углеперерабатывающие фабрики	Мощность угольных шахт
	В1	В2	В3	В4
	Расстояние от шахт до углеперерабатывающих фабрик, км
А1	24	28	44	19	250
А2	44	17	36	17	190
А3	26	39	15	21	170
А4	50	41	19	44	90
А5 (фиктивная)	0	0	0	0	390
Производственные возможности фабрик	260	210	230	390
Матрица оптимального распределения поставок угля	В1	В2	В3	В4	Вывезенное из шахт количество угля
А1	0	0	0	250	250
А2	0	136	0	54	190
А3	0	0	140	30	170
А4	0	0	90	0	90
А5 (фиктивная)	260	74	0	56	390
Поступившие на фабрику количество угля	260	210	230	390
Целевая функция (суммарные транспортные затраты на перевозку угля)	8 073 000р.

Дадим экономическую интерпретацию полученного решения.

Итак, для того, чтобы совокупные транспортные издержки на перевозку угля от шахт до перерабатывающих фабрик, осуществляющуюся с помощью железнодорожного транспорта, были минимальны и составили 8 073 тыс.руб. необходимо придерживаться следующего оптимального плана распределения поставок угля:

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

- со второй шахты 136 т. добытого угля необходимо перевезти на вторую перерабатывающую фабрику и 54 т. - на четвертую;

- с третьей шахты 140 т. добытого угля необходимо перевезти на третью перерабатывающую фабрику и 30 т. - на четвертую;

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

Кроме того, важно отметить, что согласно полученному оптимальному распределению перевозки угля производственная потребность первой перерабатывающей фабрики не будет удовлетворена на 260 т., второй фабрики - на 74 т., а четвертой - на 56 т.

3. Задача

Руководство финансовой компании рассматривает 4 инвестиционных проекта, между которыми собирается распределить 1820 млн. руб.

В зависимости от объема выделенных денежных средств , каждый инвестиционный проект приносит финансовой компании дополнительный доход , () у.е.:

Таблица 10

Объем выделенных денежных средств, x (млн. руб.)	Дополнительный доход инвестиционного проекта в зависимости от объема выделенных денежных средств, fi(x) (у.е.)
	f1(x)	f2(x)	f3(x)	f4(x)
0	0	0	0	0
364	18	9	12	12
728	30	21	17	21
1092	38	27	29	29
1456	41	41	44	36
1820	46	53	61	63

Необходимо:

1. Определить размер максимального дополнительного дохода от вложения денежных средств в рассматриваемые инвестиционные проекты.

2. Определить оптимальное распределение средств финансовой компании, обеспечивающее ей максимальный дополнительный доход от инвестиций во все проекты.

3. Дать экономическую интерпретацию полученного решения.

Решение:

1. Определим размер максимального дополнительного дохода от вложения денежных средств в рассматриваемые инвестиционные проекты.

Согласно обратной схеме Беллмана показатель эффективности 4-ого шага:

;

показатель эффективности 1-го инвестиционного проекта.

 объединённый показатель эффективности 2-х инвестиционных проектов.

Произведем вычисления значений функции и представим их в таблице 11:

Таблица 11

Объем выделенных денежных средств, x (млн. руб.)	Дополнительный доход инвестиционного проекта в зависимости от объема выделенных денежных средств, fi(x) (у.е.)	Показатели эффективности предприятий в зависимости от объема выделенных средств, E i(x) (у.е.)
	f1(x)	f2(x)	f3(x)	f4(x)	E4(x)	E 3(x)	E 2(x)	E 1(x)
0	0	0	0	0	0	0	0	0
364	18	9	12	12	12	12	12	18
728	30	21	17	21	21	24	21	30
1092	38	27	29	29	29	33	33	42
1456	41	41	44	36	36	44	44	51
1820	46	53	61	63	63	63	61	63

Объединённый показатель эффективности 3-х инвестиционных проектов

.

Произведем вычисления значений функции и представим их в таблице 11.

Объединённый показатель эффективности 4-х инвестиционных проектов -

Произведем вычисления значений функции и представим их в таблице 11.

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

.

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

2. Определим оптимальное распределение средств финансовой компании, обеспечивающее ей максимальный дополнительный доход от инвестиций во все проекты.

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

Оптимальный план №1:

Оптимальный план №2:

3. Дадим экономическую интерпретацию полученного решения.

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

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

4. Задание 4

На производственном предприятии «ТИТАН» оборудование эксплуатируется в течение лет, после чего продается (считается, что после лет оборудование в результате морального износа не способно обеспечить выпуск конкурентоспособной продукции). В начале каждого года руководство предприятия принимает решение сохранить оборудование или заменить его новым аналогичным (при этом старое оборудование продается, а вырученные средства направляются на покрытие части стоимости нового оборудования). Первоначальная стоимость нового оборудования составляет тыс. руб., затраты на содержание оборудования - тыс. руб., и ликвидная стоимость оборудования - тыс. руб. приведены в таблице:

	0	1	2	3	4	5
	770	980	1270	1570	2070	-
	-	7010	6010	4510	2410	1210

Необходимо:

1. Определить минимальные суммарные затраты производственного предприятия «ТИТАН» на эксплуатацию оборудования в течение рассматриваемого периода .

2. Определить оптимальную стратегию (план-график) эксплуатации оборудования, обеспечивающую минимальные суммарные затраты производственного предприятия «ТИТАН» на эксплуатацию в течение рассматриваемого периода T в условиях текущих цен.

3. Дать экономическую интерпретацию полученного решения.

Решение:

1. Определим минимальные суммарные затраты производственного предприятия «ТИТАН» на эксплуатацию оборудования в течение 5 лет. Проведем на размеченном графе условную оптимизацию.

5 шаг. В состояниях (5, t) оборудование продается, условный оптимальный доход от продажи равен ликвидной стоимости (t), но поскольку целевая функция связана с затратами, то в кружках точек (5, t) ставим величину дохода со знаком «-».

4 шаг.

Состояние (4,1).

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

Таким образом, если система к последнему шагу находилась в точке (4,1), то следует идти в точку (5,2) (укажем это направление пунктирной линией).

Состояние (4,2).

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

Состояние (4,3).

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

Состояние (4,4).

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

3 шаг.

Состояние (3,1).

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

В данном случае, находясь в точке (3,1), оптимально идти как в точку (4,2), так и в точку (4,1) (в обоих случаях затраты будут одинаковыми, возникает альтернативность решения).

Состояние (3,2).

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

Состояние (3,3).

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

2 шаг.

Состояние (2,1).

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

Состояние (2,2).

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



1 шаг.

Состояние (1,1).

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

После проведения условной оптимизации в точке (0,0) получим минимальные затраты на эксплуатацию оборудования в течение 5 лет с последующей продажей:

усл. ден. ед.

2. Определим оптимальную стратегию (план-график) эксплуатации оборудования, обеспечивающую минимальные суммарные затраты производственного предприятия «ТИТАН» на эксплуатацию в течение 5 лет в условиях текущих цен.

Строим оптимальные траектории, перемещаясь из точки (0,0) по пунктирным линиям в конечное состояние (рис. 28).

Получаем следующие наборы точек, соответствующие управлениям:

(0,0); (1,1); (2,1); (3,2); (4,1); (5,2) ;

(0,0); (1,1); (2,2); (3,1); (4,1); (5,2) ;

(0,0); (1,1); (2,2); (3,1); (4,2); (5,1) .

3. Дать экономическую интерпретацию полученного решения.

Согласно первой стратегии эксплуатации оборудования, обеспечивающей минимальные суммарные затраты производственного предприятия «ТИТАН» на эксплуатацию в течение 5 лет, его следует заменить в начале 2-ого и 4-ого года, согласно второй стратегии - в начале 3-его и 4-ого года, согласно третьей стратегии - в начале 3-его и 5-ого года.

Рис. Размеченный граф условной оптимизации

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

...