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

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

1. Составить экономико-математические модели задач

1.1 Предприятие химической чистки и крашения располагает тремя видами производственных ресурсов: трудо-часы, химические материалы, машино-часы. математический линейный программирование

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

Производственные ресурсы	Затраты ресурсов по каждому технологическому способу	Наличный объем ресурсов
	I	II
1	14	10	12
2	5	10	10
3	60	70	80
Объем реализации	60	45

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

Решение

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

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

Тогда суммарный объем реализации составит 60x1 д.е. от реализации 1-го технологического способа и 45x2 от реализации 2-го технологического способа, то есть

F = 60x1 + 45x2 (1)

Составим систему ограничений по ограничениям производственных ресурсов:

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

F = 60x1 + 45x2

1.2 Решить задачи линейного программирования графическим методом и провести анализ на чувствительность

Решение

Запишем уравнения граничных прямых и построим их на плоскости x1ox2.

Рассмотрим целевую функцию задачи = x1-4x2 > min.

Построим прямую, отвечающую значению функции = 0: = x1-4x2 = 0.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации .

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

Рис. 1 Решение ЗЛП геометрическим способом

Задача не имеет допустимых решений. ОДР представляет собой бесконечное множество (не ограничена).

1.3 Решить задачи линейного программирования с n переменными графическим методом

Решение

Система ограничений ЗЛП задана системой уравнений. Все уравнения системы линейно независимые, поэтому число базисных переменных равно 4, а число свободных переменных равно 2.

В качестве свободных переменных выберем переменные x1 и x2, а базисные переменные x3, x4 выразим через них, то есть приведем систему уравнений к единичному базису.

Целевую функцию выразили через свободные переменные x1 и x2, то есть так как по условию задачи x3, x4 ? 0.

Итак, получили ЗЛП с двумя переменными: L = > mах

Рассмотрим целевую функцию задачи = x1+x2-8 > min.

Построим прямую, отвечающую значению функции = 0: = x1+x2-8 = 0.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации . Начало вектора - точка (0; 0), конец - точка (1; 1).

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

На графике эта прямая обозначена пунктирной линией.

ОДР представляет собой бесконечное множество (не ограничена).

Точку максимума не имеет.

Перемещая прямую L = 0 в направлении вектора , находим минимальную точку А. Точка А - начало координат.

x1 = 0, x2 = 0

Lmin =

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

Решение

Базисные переменные системы ограничений и целевую функцию выразим через свободные переменные x1, x2 и х3.

Получим:

Найдем первое допустимое решение, положив свободные переменные равные нулю x1 = 0, x2 = 0, x3 = 0, тогда x4 = -4, x5 = 1, то есть , при котором L1 = 0.

Выясним, является ли оно оптимальным. Из выражения L = видно, что L можно увеличить за счет увеличения переменной x2.

Из первого уравнения системы ограничений видно, что переменную x2 можно увеличить до (-4), а из второго уравнения системы видно, что x2 можно увеличить до 1.

Из этих 2-х значений выбираем большее, чтобы обеспечить неотрицательность всех базисных переменных.

Итак, x2 = 1, тогда

Систему ограничений и целевую функцию L выразим через новые свободные переменные.

Получим: L =

Получили второе допустимое решение

Выясним, является ли оно оптимальным.

Систему ограничений и целевую функцию L выразим через новые свободные переменные.

Получим: L =

Из выражения L = видно, что L можно увеличить за счет увеличения переменной x3.

Из первого уравнения системы ограничений видно, что переменную x3 можно увеличить до 1, а из второго уравнения системы видно, что x3 нельзя увеличить.

Итак, x3 = 1, тогда

Получили третье допустимое решение 2

Систему ограничений и целевую функцию L выразим через новые свободные переменные.

Получим: L =

Больше L увеличить нельзя (

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

1.5 Решить задачи линейного программирования табличным симплекс-методом и провести анализ на чувствительность

Решение

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

Для этого воспользуемся методом Жордана-Гаусса.

Таблица 1.1

Базис	X1	X2	X3	X4	Свободн. члены
	2	2	3	0	9
	0	1	2	1	4
	1	2	2	2	8
L	-3	-2	-1	-1	0

Выберем в качестве базисной переменной x1. Тогда столбец при этой переменной будет разрешающим. Выберем разрешающий элемент как наименьшее отношение между элементами столбца свободных членов и соответствующими положительными элементами разрешающего столбца. Таким элементом будет 2 в 1-й строке.

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

Таблица 1.2

Базис	X1	X2	X3	X4	Свободные члены
X1	1	1,0	1,5	0,0	4,5
	0	1,0	2,0	1,0	4,0
	0	1,0	0,5	2,0	3,5
L	0	1,0	3,5	-1,0	13,5

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

Таблица 1.3

Базис	X1	X2	X3	X4	Свободные члены
X1	1	0	1,0	-2,00	1
	0	0	1,5	-1,00	0,5
Х2	0	1	0,5	2,00	3,5
L	0	0	3,0	-3,00	10

Таблица 1.4

Базис	X1	X2	X3	X4	Свободные члены
X1	1	0	0	-1,33	0,67
Х3	0	0	1	-0,67	0,33
Х2	0	1	0	2,33	3,33
L	0	0	0	-1,00	9,00

Задача имеет допустимое решение - Х = (0,67; 3,33; 0,33; 0).

Это решение является оптимальным, так как в строке L нет положительных элементов.

Хоптим. = (0,67; 3,33; 0,33; 0)

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

Решение

Соответствующая ей двойственная задача запишется в виде:

Исходную ЗЛП решим двойственным симплексным методом и графическим методом, а двойственную ЗЛП решим табличным симплексным методом и сравним решения.

В 1-м неравенстве смысла (?) вводим базисную переменную x4.

В 2-м неравенстве смысла (?) вводим базисную переменную x5.

Используя алгоритм двойственного симплексного метода, найдем решение исходной ЗЛП.

Базис	Своб.	x1	x2	x3	x4	x5
x4	-1	-1	-2	1	1	0
x5	-4	-2	3	-3	0	1
	0	-8	-6	-3	0	0
и	0	-8 : (-2) = 4	-	-3 : (-3) = 1	-	-
Базис	Своб.	x1	x2	x3	x4	x5
X4	-21/3	-12/3	-1	0	1	1/3
X3	11/3	2/3	-1	1	0	-1/3
	4	-6	-9	0	0	-1
и	0	-6 : (-12/3) = 33/5	-9 : (-1) = 9	-	-	-

Базис	Своб.	x1	x2	x3	x4	x5
X1	12/5	1	3/5	0	-3/5	-1/5
X3	2/5	0	-12/5	1	2/5	-1/5
	122/5	0	-52/5	0	-33/5	-21/5

Результирующая таблица определяет допустимое оптимальное решение исходной ЗЛП:

Решение двойственной задачи получим из строки L результирующей таблицы с учетом соответствия между переменными исходной и двойственной задач:

Для решения двойственной ЗЛП табличным симплексным методом, приведем ее к виду:

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

Баз.	Cвоб. члены	Y1	Y2	Y3	Y4	У5
Y3	8	1	2	1	0	0
Y4	6	2	-3	0	1	0
У5	3	-1	3	0	0	1
	0	-1	-4	0	0	0

Баз.	Cвоб. члены	Y1	Y2	Y3	Y4	У5
Y3	6	12/3	0	1	0	-2/3
Y4	9	1	0	0	1	1
У2	1	-1/3	1	0	0	1/3
	4	-21/3	0	0	0	11/3

Баз.	Cвоб. члены	Y1	Y2	Y3	Y4	У5
Y1	33/5	1	0	3/5	0	-2/5
Y4	52/5	0	0	-3/5	1	12/5
У2	21/5	0	1	1/5	0	1/5
	122/5	0	0	12/5	0	2/5

Получили оптимальное решение двойственной ЗЛП:

Из последней симплексной таблицы из строки получим решение исходной ЗЛП:

Двойственную ЗЛП решим графическим методом.

Область допустимых решений представляет собой многоугольник АВДЕC.

Прямая = const пересекает область в точке E. Так как точка Д получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: у1 = 3,6, у2 =2,2.

Откуда найдем максимальное значение целевой функции:

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

На двух складах А и В находится по 90 т. горючего. Перевозка одной тонны горючего со склада А в пункты 1, 2, 3 соответственно стоит 1, 3 и 5 д.е., а перевозка одной тонны со склада В в те же пункты - соответственно 2, 5 и 4 д.е.

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

Решение

поставщики	потребители	запас
	В1	В2	В3
А1	1	3	5	90
А2	2	5	4	90
спрос	60	60	60

поставщики	потребители
	В1	В2	В3
А1	1 х11	3х12	5 х13	90
А2	2 Х21	5Х22	4 Х23	90
спрос	60	60	60

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

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

Попутно отметим, что план является невырожденным, т. к. число занятых клеток (9) равно m+? n-1=3+2-1=4.

поставщики	потребители
	В1	В2	В3
А1	1 601	3302	5	90
А2	2	5 304	4 603	90
спрос	60	60	60

F(x) = 60*1+30*3+30*5+60*4 = 540 д.е.

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

Этап II. Улучшение опорного плана.

Проверка опорного плана на оптимальность.

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

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

Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Дij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки хij=1 от поставщика Аi к потребителю Вj.

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

Величина Дij называется оценкой свободной клетки (или характеристика).

В исходном решении задачи имеются клетки свободные от поставок.

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

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

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

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

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

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

Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками Дij, то за один переход к лучшему плану можно занять поставкой только одну клетку - ту, которая обеспечивает наибольшее снижение целевой функции.

Шаг 1. Определяем оценку для каждой свободной клетки.

(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	Запасы
1	1[60]	3[30][-]	5[+]	90
2	2	5[30][+]	4[60][-]	90
Потребности	60	60	60

Цикл приведен в таблице (1,3; 1,2; 2,2; 2,3; ).

Оценка свободной клетки равна Д13 = (5) - (3) + (5) - (4) = 3.

(2;1): В свободную клетку (2;1) поставим знак «+».

	1	2	3	Запасы
1	1[60][-]	3[30][+]	5	90
2	2[+]	5[30][-]	4[60]	90
Потребности	60	60	60

Цикл приведен в таблице (2,1; 2,2; 1,2; 1,1; ).

Оценка свободной клетки равна Д21 = (2) - (5) + (3) - (1) = -1.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (2,1;) равные: (-1).

Переход от неоптимального опорного плана к лучшему.

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

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	Запасы
1	1[30]	3[60]	5	90
2	2[30]	5	4[60]	90
Потребности	60	60	60

1*30 + 3*60 + 2*30 + 4*60 = 510

Шаг 2. Определяем оценку для каждой свободной клетки.

(1;3): В свободную клетку (1;3) поставим знак «+».

	1	2	3	Запасы
1	1[30][-]	3[60]	5[+]	90
2	2[30][+]	5	4[60][-]	90
Потребности	60	60	60

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,3; ).

Оценка свободной клетки равна Д13 = (5) - (1) + (2) - (4) = 2.

(2;2): В свободную клетку (2;2) поставим знак «+».

	1	2	3	Запасы
1	1[30][+]	3[60][-]	5	90
2	2[30][-]	5[+]	4[60]	90
Потребности	60	60	60

Цикл приведен в таблице (2,2; 2,1; 1,1; 1,2; ).

Оценка свободной клетки равна Д22 = (5) - (2) + (1) - (3) = 1.

Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции F невозможно, поскольку она достигла минимального значения.

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

Минимальные затраты составят:

1*30 + 3*60 + 2*30 + 4*60 = 510

2) Для исследования плана ТЗ на оптимальность сначала по занятым клеткам для нахождения потенциалов поставщиков и потребителей составляется и решается система уравнений вида Ui + Vj = , далее для всех незанятых клеток вычисляются оценки Sij по формуле: ij = Сij - (Ui + Vj ).

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

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

Если все оценки S неотрицательны, то план является оптимальным. Если все оценки S, то оптимальный план единственен.

Если хотя бы одна оценка S, то ТЗ имеет бесконечное множество оптимальных планов с одним и тем же значением целевой функции.

Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой S . Если таких клеток несколько, то обычно выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой.

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

Потенциалы подсчитаем непосредственно в таблице. Положим V2=0.

поставщики	потребители
	60	60	60
90	1 60 -	3 30 +	5	1=3
90	2 +	5 30 -	4 60	2=5
спрос	V1=-2	V2=0	V3=-1

13 = 5- (3-1) = 3 21 = 2 - (5-2) = -1

Так как среди оценок есть отрицательная, то план не является оптимальным. Надо улучшать план, загружая клетку (2,1).

Min (30, 60) = 30

поставщики	потребители
	60	60	60
90	1 30	360	5	1=3
90	2 30	5	4 60	2=4
спрос	V1=-2	V2=0	V3=0

13 = 5- (3+0) = 2 22 = 5 - (4+0) = 1

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

Fmin = 30*1+60*3+30*2+60*4 = 510 ден. ед.

ХОПТИМ. =

Список использованных источников

1 Кремер Н.М. Исследование операций в экономике. - М.: ЮНИТИ, 1997.

2 Вентцель Е.С. Исследование операций. - М.: Советское радио, 1972.

3 Руководство к решению задач с экономическим содержанием по курсу высшей математики / Под ред. А.И. Карасева и Н.Ш. Кремера. - М.: ВЗФЭИ, 1989.

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

5 Акулич И. Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1993.

6 Калихман И.Л Сборник задач по математическому программированию. - М.: Высшая школа, 1975.

7 Федосеев В.В. Экономико-математические методы и прикладные модели. - М.: ЮНИТИ, 1999.

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

...