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

2

Экономико-математические методы и модели

Содержание

Задача №1

Задача №2

Задача №3

Задача №4

Список использованной литературы

решение модель выпуск прибыль транспорт

Задача №1

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

А - матрица норм затрат сырья;

В - запасы ресурсов;

С - прибыль на единицу продукции

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

Решение задачи.

Обозначим через х1 количество единиц продукции первого вида, а через x2 - количество единиц продукции второго. Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений:

1*x1+3*x2<=90

4*x1+2*x2<=120

1*x1+1*x2<=40

x1,x2 >=0; - условие неотрицательности переменных.

Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных х1 и x2. Реализация х1 единиц продукции первого вида и x2 единиц продукции второго дает соответственно 5х1 и 2x2 ден. ед. прибыли, суммарная прибыль С = 5х1 + 2x2. Условиями не оговорена неделимость единицы продукции, поэтому х1 и x2 (план выпуска продукции) могут быть и дробными числами. Требуется найти такие х1 и x2, при которых функция С достигает максимум, т.е. найти максимальное значение линейной функции С = 5х1 + 2x2 при ограничениях.

Математическая модель задачи:

Сmax = 5х1 + 2x2

Система ограничений:

1*x1+3*x2<=90

4*x1+2*x2<=120

1*x1+1*x2<=40

x1,x2 >=0; - условие неотрицательности переменных.

Решение задачи с использованием графического симплекс-метода.

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

Неравенство	x11	x21	x12	x22
1*x1+3*x2<=90	90	0	0	30
4*x1+2*x2<=120	30	0	0	60
1*x1+1*x2<=40	40	0	0	40

Построим вектор целевой функции C(5;2). Система координат с областью допустимых решений OABCD и вектором целевой функции C приведена на рис.

Рис. График области допустимых решений.

Построим линию уровня 5x1+2x2 = 0, проходящую через начало координат и перпендикулярную вектору C (5;2). Будем передвигать ее в направлении вектора С, в результате чего находим точку, в которой функция принимает максимальное значение - точку D. При дальнейшем перемещении она уже не будет иметь общих точек с областью допустимых решений OABCD. Точка D имеет координаты (30;0). Сmax = 5*30+2*0=150

Ответ: Для того чтобы получить максимальную прибыль в размере 150 ден. ед., необходимо запланировать производство 30 ед. продукции первого вида, а продукцию второго вида не выпускать совсем.

Задача №2

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

Решение задачи.

Математическая модель задачи:

Сmax = 5х1 + 2x2

Система ограничений:

1*x1+3*x2<=90

4*x1+2*x2<=120

1*x1+1*x2<=40

x1,x2 >=0; - условие неотрицательности переменных.

Решение задачи с использованием метода симплекс-таблиц.

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

Целевая функция:

С max = 5*x1+2*x2+0*x3+0*x4+0*x5

Система ограничений:

1*x1+3*x2+x3=90

4*x1+2*x2+x4=120

1*x1+1*x2+x5=40

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

P0 - вектор свободных коэффициентов

Pi - вектор коэффициентов при переменной хi

Расширенная целевая функция:

С max = 5*x1+2*x2+0*x3+0*x4+0*x5

Вектора:

P0	P1(x1)	P2(x2)	P3(x3)	P4(x4)	P5(x5)
90	1	3	1	0	0
120	4	2	0	1	0
40	1	1	0	0	1

Базисными могут быть только единичные вектора. Базис:

Базисный вектор №1: P3(x3)

Базисный вектор №2: P4(x4)

Базисный вектор №3: P5(x5)

Заполним первую таблицу:

№	Базис	Коэффициенты при базисе	P0	5	2	0	0	0
				P1	P2	P3	P4	P5
1	P3	0	90	1	3	1	0	0
2	P4	0	120	4	2	0	1	0
3	P5	0	40	1	1	0	0	1
С max =	0	-5	-2	0	0	0

При просмотре последней (индексной) строки среди коэффициентов этой строки (исключая столбец свободных членов) находим наименьшее отрицательное число: -5 (первый столбец - ключевой).

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

Замещаемый базисный вектор: P4 (2-я строка)

Новый базисный вектор: P1 (1-й столбец)

Заменяем базисный вектор P4 на P1.

Строим новую таблицу, содержащую новые названия базисных переменных, для этого:

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

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

- в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

- столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

- строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.

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

В результате получили новую симплекс-таблицу, отвечающую новому базисному решению:

№	Базис	Коэффициенты при базисе	P0	5	2	0	0	0
				P1	P2	P3	P4	P5
1	P3	0	60	0	2.5	1	-0.25	0
2	P1	5	30	1	0.5	0	0.25	0
3	P5	0	10	0	0.5	0	-0.25	1
С max =	150	0	0.5	0	1.25	0

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

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

x1	x2	x3	x4	x5
30	0	60	0	10

Целевая функция:

C max = 5*30+2*0

И в результате: Ответ: Для того чтобы получить максимальную прибыль в размере 150 ден. ед., необходимо запланировать производство 30 ед. продукции первого вида, а продукцию второго вида не выпускать совсем (ответ совпадает с ответом, полученным графическим методом).

Задача №3

Транспортная задача открытого типа.

В регионе расположено несколько НГДУ, обеспечивающих определённые объёмы добычи нефти, которая поступает в НПЗ, расположенные в различных регионах страны и имеющие различные производственные мощности. В силу разноудалённости потребителей от НГДУ затраты на транспортировку нефти различаются.

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

Введены условные обозначения:

i - индекс НГДУ, i=1,m

m - общее число НГДУ в регионе

j - индекс НПЗ, j=1,n

n - общее число НПЗ.

Известно:

- объёмы добычи нефти в i-ом НГДУ, тыс.т.;

- потребность j-го НПЗ в нефти, тыс.т.;

- издержки на транспортировку 1000 т. нефти, тыс. руб.

	180	190	110	210	200	120
490	5	7	8	4	6	9
270	7	2	5	8	6	7
380	5	4	7	6	9	8

Модель задачи. В качестве неизвестных задачи принимаются переменные , означающие объём перевозок нефти i-го НГДУ к j-му НПЗ. В качестве коэффициентов целевой функции выступают издержки на перевозку 1000 т. нефти. Целевая функция минимизируется. Модель задачи записывается в общем виде, при этом необходимо учесть, что по исходным данным задача является открытой.

Имеем транспортную задачу с избытком запасов:

аi > bj ( где i=1..m ; j=1..n ).

490+270+380>180+190+110+210+200+120

1140>1010

C max = 150;

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

_n

X_i,j a_i (i=1, ... , m);

^j=1

^m

Xi,j = bj (j=1, ... , n).

ⁱ⁼¹

Мы получаем следующую задачу:

х₁₁+х₁₂+х₁₃+х₁₄+х₁₅+х₁₆ 490

х₂₁+х₂₂+х₂₃+х₂₄+х₂₅+х₂₆ 270

х₃₁+х₃₂+х₃₃+х₃₄+х₃₅+х₃₆ 380

х₁₁+х₂₁+х₃₁ = 180

х₁₃+х₂₃+х₃₃ = 190

х₁₄+х₂₄+х₃₄ = 110

х₁₂+х₂₂+х₃₂ = 210

х₁₅+х₂₅+х₃₅ = 200

х₁₆+х₂₆+х₃₆ = 120

х_ij 0 для i = 1,2,3; j = 1,2,3,4,5,6;

К_min=5х₁₁+7х₁₂+8х₁₃+4х₁₄+6х₁₅+9х₁₆+7х₂₁+2х₂₂+5х₂₃+8х₂₄+6х₂₅+7х₂₆+5х₃₁+4х₃₂+7х₃₃+ +6х₃₄+9х₃₅+8х₃₆;

Решение задачи.

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

Для этого, сверх имеющихся n пунктов назначения В₁, B₂, ... , B_n, введём ещё один, фиктивный, пункт назначения B_n+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

и_т+1 = а_ш - и ( где ш=1бюююбь ж о=1бюююбт ) б

b₇ = 1140 - 1010= 130,

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

назначения B_n+1 с его заявкой b_n+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

Первоначальный опорный план поставок построим на основе метода северо-западного угла:

bjai	180	190	110	210	200	120	130
490	5		7		8		4		6		9		0
		180		190		110		10
270	7		2		5		8		6		7		0
								200		70
380	5		4		7		6		9		8		0
										130		120		130

Стоимость перевозок по данному плану составляет: 7300 тыс. руб.

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

Для этого плана можно определить платежи (_i и _j ), так, чтобы в каждой базисной клетке выполнялось условие :

_i + _j = с_i,j (*)

Уравнений (*) всего m + n - 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений (*) можно найти остальные платежи _i , _j , а по ним вычислить псевдостоимости: u_i,j= _i + _j для каждой свободной клетки.

Если оказалось, что все эти псевдостоимости не превосходят стоимостей u_i,j ? с_i,j ,

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

bjai	180	190	110	210	200	120	130	i
490	5		7		8		4		6		9		0		0
	5	180	7	190	8	110	4	10	2		1		-7
270	7		2		5		8		6		7		0		4
	9		11		12		8	200	6	70	5		-3
380	5		4		7		6		9		8		0		7
	12		14		15		11		9	130	8	120	0	130
?i	5	7	8	4	2	1	-7

Мы получили в семи клетках _i,j ? с_i,j , теперь можно построить цикл в любой из этих клеток. Выгоднее всего строить цикл в той клетке, в которой разность _i,j ? с_i,j максимальна. В нашем случае для построения цикла берем клетку (3,2):

bjai	180	190	110	210	200	120	130	i
490	5		7	-130	8		4	+130	6		9		0		0
	5	180	7	190	8	110	4	10	2		1		-7
270	7		2		5		8	-130	6	+130	7		0		4
	9		11		12		8	200	6	70	5		-3
380	5		4	+130	7		6		9	-130	8		0		7
	12		14		15		11		9	130	8	120	0	130
?i	5	7	8	4	2	1	-7

Теперь будем перемещать по циклу число 130, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком -. При перемещении мы будем вычитать 130 из клеток со знаком - и прибавлять к клеткам со знаком + .

После этого необходимо подсчитать потенциалы _i и _j и цикл расчетов повторяется:

Стоимость перевозок по данному плану составляет: 6000 тыс. руб.

bjai	180	190	110	210	200	120	130	i
490	5		7	-60	8		4	+60	6		9		0		0
	5	180	7	60	8	110	4	140	2		11		3
270	7		2	+60	5		8	-60	6		7		0		4
	9		11		12		8	70	6	200	15		7
380	5		4		7		6		9		8		0		-3
	2		4	130	5		1		-1		8	120	0	130
?i	5	7	8	4	2	11	3

bjai	180	190	110	210	200	120	130	i
490	5		7		8	-10	4	+10	6		9		0		0
	5	180	-2		8	110	4	200	2		2		-6
270	7		2		5	+10	8	-10	6		7		0		4
	9		2	60	12		8	10	6	200	6		-2
380	5		4		7		6		9		8		0		6
	11		4	130	14		10		8		8	120	0	130
?i	5	-2	8	4	2	2	-6

Стоимость перевозок по данному плану составляет: 5460 тыс. руб.

bjai	180	190	110	210	200	120	130	i
490	5		7		8	-100	4		6	+100	9		0		0
	5	180	5		8	100	4	210	9		9		1
270	7		2		5	+100	8		6	-100	7		0		-3
	2		2	60	5	10	1		6	200	6		-2
380	5		4		7		6		9		8		0		-1
	4		4	130	7		3		8		8	120	0	130
?i	5	5	8	4	9	9	1

Стоимость перевозок по данному плану составляет: 5390 тыс. руб.

bjai	180	190	110	210	200	120	130	i
490	5	-100	7		8		4		6	+100	9		0		0
	5	180	2		5		4	210	6	100	6		-2
270	7		2	+100	5		8		6	-100	7		0		0
	5		2	60	5	110	4		6	100	6		-2
380	5	+100	4	-100	7		6		9		8		0		2
	7		4	130	7		6		8		8	120	0	130
?i	5	2	5	4	6	6	-2

Стоимость перевозок по данному плану составляет: 5090 тыс. руб.

bjai	180	190	110	210	200	120	130	i
490	5		7		8		4		6		9		0		0
	5	80	4		7		4	210	6	200	8		0
270	7		2		5		8		6		7		0		-2
	3		2	160	5	110	2		4		6		-2
380	5		4		7		6		9		8		0		0
	5	100	4	30	7		4		6		8	120	0	130
?i	5	4	7	4	6	8	0

Стоимость перевозок по данному плану составляет: 4890 тыс. руб. Псевдостоимости u_i,j = _i + _j для всех свободных клеток не превышают стоимостей, план оптимален.

К_min=4890

Ответ: план закрепления поставщиков за потребителями, который учитывает, по возможности, наиболее полное удовлетворение потребителей НПЗ и при этом обеспечивает минимальные затраты на транспортировку нефти представлен ниже (Стоимость перевозок по данному плану составляет 4890 тыс. руб.):

bjai	180	190	110	210	200	120	130
490	5		7		8		4		6		9		0
		80						210		200
270	7		2		5		8		6		7		0
				160		110
380	5		4		7		6		9		8		0
		100		30								120		130

Задача №4

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

Решение задачи.

Первоначальный опорный план поставок построим на основе метода минимальной стоимости.

bjai	180	190	110	210	200	120	130
490	5		7		8		4		6		9		0
								210		150				130
270	7		2		5		8		6		7		0
				190		80
380	5		4		7		6		9		8		0
		180				30				50		120

Стоимость перевозок по данному плану составляет: 5040 тыс. руб.

Применяем метод потенциалов.

bjai	180	190	110	210	200	120	130	i
490	5		7		8		4		6	+50	9		0	-50	0
	2		1		4		4	210	6	150	5		0	130
270	7		2		5		8		6		7		0		1
	3		2	190	5	80	5		7		6		1
380	5		4		7		6		9	-50	8		0	+50	3
	5	180	4		7	30	7		9	50	8	120	3
?i	2	1	4	4	6	5	0

bjai	180	190	110	210	200	120	130	i
490	5		7		8		4		6		9		0		0
	5		4		7		4	210	6	200	8		0	80
270	7		2		5		8		6		7		0		-2
	3		2	190	5	80	2		4		6		-2
380	5		4		7		6		9		8		0		0
	5	180	4		7	30	4		6		8	120	0	50
?i	5	4	7	4	6	8	0

Стоимость перевозок по данному плану составляет: 4890 тыс. руб. Псевдостоимости

u_i,j = _i + _j для всех свободных клеток не превышают стоимостей, план оптимален (стоимость совпадает с полученной стоимостью задачи №3, но план перевозок альтернативен).

Ответ: план закрепления поставщиков за потребителями, который учитывает, по возможности, наиболее полное удовлетворение потребителей НПЗ и при этом обеспечивает минимальные затраты на транспортировку нефти представлен ниже (Стоимость перевозок по данному плану составляет 4890 тыс. руб.):

bjai	180	190	110	210	200	120	130
490	5		7		8		4		6		9		0
								210		200				80
270	7		2		5		8		6		7		0
				190		80
380	5		4		7		6		9		8		0
		180				30						120		50

Список использованной литературы

1. Ашманов С.А. Линейное программирование. - М.: Наука, 1981.

2. Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 2006

3. Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая школа, 1967.

4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.: Высшая школа, 1980.

5. Нит И.В. Линейное программирование. - М.: Изд-во МГУ, 1978.

6. Тарасенко Н.В. Математика-2. Линейное программирование: курс лекций. - Иркутск: изд-во БГУЭП, 2003.

7. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория и конечные методы. - М.: Физматиз, 1963.

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