Основы экономико-математического моделирования

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

Санкт-Петербургский политехнический университет Петра Великого

Институт промышленного менеджмента, экономики и торговли

Высшая школа промышленного менеджмента и экономики

Курсовая работа по дисциплине: «Исследование операций»

Выполнил

студент

гр. 337332/0303

Руководитель

Старший преподаватель Е.Г. Найденышева

Санкт-Петербург 2017



Введение

Постановка задачи:

Промышленное предприятие может изготавливать три вида изделий A, B, C, используя при этом три основных, т.е. определяющих программу выпуска ресурсов R₁, R₂, R₃. Нормы расхода ресурсов на единицу изделий каждого вида, запасы ресурсов на месяц, себестоимость изготовления единицы изделия и их цены приведены в табл.1. По требованиям технологии ресурс R₃ должен быть полностью израсходован в течение месяца. Необходимо сформировать план выпуска изделий на месяц, применяя следующие критерии:

1. Максимум получаемой прибыли.

2. Минимум себестоимости изготовления изделий.

Таблица 1 Исходные данные

Наименование показателей	Нормы расхода ресурсов на одно изделие	Запасы ресурсов
	A	B	C
Ресурс R1 Ресурс R2 Ресурс R3	1 2 3	1 2 2	3 4 6	27 34 35
Себестоимость изготовления изделий, тыс.руб.	11	16	18
Цена единицы изделия, тыс.руб.	14	19	18
Прибыль от реализации единицы продукции, тыс.руб.	3	3	5



Основная часть

Задача 1

Построить соответствующие экономико-математические модели рассматриваемых однокритериальных и многокритериальных задач.

Экономико-математическая модель для функции «выручка»:

х₁ - количество продукции А;

х₂ - количество продукции В;

х₃ - количество продукции С.

Целевая функция выглядит следующим образом:

С₁(х) = 14х₁+19х₂+23х₃ > max

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

,

Экономико-математическая модель для функции «себестоимость»:

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

С₂(х) = 11х₁+16х₂+18х₃ > min

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

,

Экономико-математическая модель для функции «прибыль»:

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

С₃(х) = 3х₁+3х₂+5х₃ > max

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

,

Экономико-математическая модель для многокритериальной задачи (себестоимость и прибыль):

Целевые функции:

С₂(х) = 11х₁+16х₂+18х₃ > min

С₃(х) = 3х₁+3х₂+5х₃ > max

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

,

Задача 2

Решить однокритериальную задачу линейного программирования (ЗЛП) с целевой функцией «выручка» симплекс-методом. Выполнить послеоптимизационный анализ. Целочисленное решение получить методом Гомори и методом ветвей и границ. экономика себестоимость прибыль

Решение:

х₁ - количество продукции А;

х₂ - количество продукции В;

х₃ - количество продукции С.

Целевая функция выглядит следующим образом:

С₁(х) = 14х₁+19х₂+23х₃ > max

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

,

Запишем задачу в канонической форме:

,

В задаче отсутствует единичный базис. Применим метод искусственного базиса.

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

() = -х₆ > max

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

,

БДП вспомогательной задачи: = (0;0;0;27;34;35). Симплекс-таблица для вспомогательной задачи представлена в таблице 2:

Таблица 2. Решение вспомогательной задачи

	0	0	0	0	0	-1
Су	Базис	А0=b	А1	А2	А3	А4	А5	А6
0 0 -1	А4 А5 <А6	27 34 35	1 2 3	1 2 2	3v 4 6	1 0 0	0 1 0	0 0 1
	()/?j	-35	-3	-2	-6	0	0	0
0 0 0	А4 А5 А3	19/2 32/3 35/6	-1/2 0 1/2	0 2/3 1/3	0 0 1	1 0 0	0 1 0	Ѕ 2/3 1/6
	()/?j	0	0	0	0	0	0	1

На второй итерации получен оптимальный план вспомогательной задачи: х⁰ = (0; 0; 35/6; 19/2; 32/3), о чем свидетельствуют неотрицательные двойственные оценки и отсутствие отрицательных компонент в столбце А₀.

Оптимальный план вспомогательной задачи будет использоваться как начальное БДП для основной задачи. Для этого пересчитаем двойственные оценки основной задачи, используя начальный БДП х⁰ = (0; 0; 35/6; 19/2; 32/3).

Таблица 3 Решение основной задачи

			14	19	23	0	0
Су	Базис	А0=b	А1	А2	А3	А4	А5
0 0 23	А4 <А5 А3	19/2 32/3 35/6	-1/2 0 1/2	0v 2/3 1/3	0 0 1	1 0 0	0 1 0
	С(х)/ ?j	805/6	-5/2	-34/3	0	0	0
0 19 23	А4 А2 <А3	19/2 16 1/2	-1/2v 0 1/2	0 1 0	0 0 1	1 0 0	0 3/2 -1/2
	С(х)/ ?j	631/2	-5/2	0	0	0	17
0 19 14	А4 А2 А1	10 16 1	0 0 1	0 1 0	1 0 2	1 0 0	-1/2 3/2 -1
	С(х)/ ?j	318	0	0	5	0	14,5

На первой итерации минимальная из отрицательных двойственных оценок: -34/3, значит А₂ вводится в базис, А₅ выводится. После пересчета таблицы есть одна отрицательная двойственная оценка, поэтому столбик А₁ вводится в базис, А₃ выводится. На третьей итерации нет отрицательных двойственных оценок и отрицательных компонент в столбце А₀, значит получен оптимальный план основной задачи: х* = (1; 16; 0; 10; 0) и значение целевой функции С(х*) = 318. Задача решена.

Послеоптимизационный анализ.

1. Интервал устойчивости.

Общая формула:

S_k = (b_k + ?b_k^min; b_k + ?b_k^max)

Интервал устойчивости S_k показывает, как может изменяться значение b_k, чтобы структура оптимального плана не изменялась.

S₁ = (b₁ + ?b₁^min; b₁ + ?b₁^max)

k= 1; n = 3; n+k = 4; b₁ = 27.

?b₁^min = -10/1 = -10

?b₁^max = +?

S₁ = (27+ (-10)); 27 + ?) = (17; +?).

S₂ = (b₂ + ?b₂^min; b₂ + ?b₂^max)

k= 2; n = 3; n+k = 5; b₁ = 34.

?b₂^min = -16 : 3/2 = -32/3 = - 10

?b₂^max = min { -10 : (-1/2); -1 : (-1)} = min {20;1} = 1

S₂ = (34 + (- 10 ); 34 + 1) = (24 ; 35)

Ресурс R3 расходуется полностью, поэтому интервал устойчивости для него - одно число, равное 35.

2. Интервал оптимальности.

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

Общая формула:

P_k = [ C_k + ?C_k^min; C_k + ?C_k^max]

P₁ = [ C₁ + ?C₁^min; C₁ + ?C₁^max]

С₁ = 14

?C₁^min = -5/1 = -5

?C₁^max = -29/2 : (-1/2) = 29

P₁ = [ 14 + (-5); 14 +29] = [9;43]

P₂ = [ C₂ + ?C₂^min; C₂ + ?C₂^max]

С2 = 19

?C₂^min = -29/2: 3/2 = -29/3 = -9

?C₂^max = +?

P₂ = [19+ (-9 ); 19+?] = [10; +?]

P₃ = [ C₃ + ?C₃^min; C₃ + ?C₃^max]

С3 = 23

?C₃^min = -5/2 = -2,5

?C₃^max =-29/2 : (-1) = 29/2 = 14,5

P₃ = [23+ (-2,5); 23+ 14,5] = [20,5; 37,5]

3. Избыточные и дефицитные ресурсы.

Находятся для оптимального плана.

х* = (1;16;0;10;0)

х₄ - количество ресурса R₁ на складе после производства

х₅ - количество ресурса R₂ на складе после производства.

х₄* = 10, значит после производства на складе осталось 10 единиц ресурса R₁, то есть R1 - избыточный ресурс относительно этого оптимального плана.

х₅* = 0, значит после производства на складе не осталось ресурса R₂, то есть R₂ - дефицитный ресурс.

Ресурс R3 не остаётся на складе после производства, так как должен быть полностью использован.

Задача 3

Решить однокритериальную задачу линейного программирования с целевой функцией «прибыль» геометрически.

Решение:

х₁ - количество продукции А;

х₂ - количество продукции В;

х₃ - количество продукции С.

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

С₃(х) = 3х₁+3х₂+5х₃ > max

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

,

Выразим третью переменную из третьего ограничения:

х₃=

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

С₃(х) = -3х₁+8х₂+175> max

,

Чтобы решить задачу графически, необходимо решить систему неравенств. На рисунке 1 отображено решение системы неравенств, градиент и линии уровня целевой функции. Решением задачи является точка пересечения первого и второго ограничений, на графике обозначена буквой А и имеет координаты (1;16)

Рисунок 1 - графическое решение задачи

Полученные значения х₁ и х₂ необходимо подставить в х₃, которое ранее было выражено из третьего ограничения: х3 = 0.

Ответ: х₁* = 1; х₂* = 16, х₃* = 0, С₃(х*) = 51.

Задача 4

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

Цена каждой единицы изделия (с_j, j = 1,2,3) может изменяться, причем эти изменения определяются соотношениями:

с₁= 14-л; с₂ = 19+л; с₃ = 23+2л,

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

Решение:

х₁ - количество продукции А;

х₂ - количество продукции В;

х₃ - количество продукции С.

Целевая функция выглядит следующим образом:

С₁(х) = 14х₁+19х₂+23х₃ > max

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

,

Запишем задачу в канонической форме:

,

В задаче отсутствует единичный базис. Применим метод искусственного базиса.

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

() = -х₆ > max

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

,

БДП вспомогательной задачи: = (0;0;0;27;34;35). Симплекс-таблица для вспомогательной задачи представлена в таблице 2:

Таблица 4 Решение вспомогательной задачи

	0	0	0	0	0	-1
Су	Базис	А0=b	А1	А2	А3	А4	А5	А6
0 0 -1	А4 А5 <А6	27 34 35	1 2 3	1 2 2	3v 4 6	1 0 0	0 1 0	0 0 1
	()/?j	-35	-3	-2	-6	0	0	0
0 0 0	А4 А5 А3	19/2 32/3 35/6	-1/2 0 1/2	0 2/3 1/3	0 0 1	1 0 0	0 1 0	Ѕ 2/3 1/6
	()/?j	0	0	0	0	0	0	1

На второй итерации получен оптимальный план вспомогательной задачи: х⁰ = (0; 0; 35/6; 19/2; 32/3), о чем свидетельствуют неотрицательные двойственные оценки и отсутствие отрицательных компонент в столбце А₀.

Оптимальный план вспомогательной задачи будет использоваться как начальное БДП для основной задачи. Для этого пересчитаем двойственные оценки основной задачи, используя начальный БДП х⁰ = (0; 0; 35/6; 19/2; 32/3).

Таблица 5 Решение основной задачи

	14	19	23	0	0
	-л	л	2л	0л	0л
Су?	Су??	Базис	А0=b	А1	А2	А3	А4	А5
0 0 23	0л 0л 2л	А4 <А5 А3	19/2 32/3 35/6	-1/2 0 1/2	0v 2/3 1/3	0 0 1	1 0 0	0 1 0
		С(х)/ ?j? С(х)/ ?j??	805/6 35/3л	-5/2 2л	-34/3 -1/3л	0 0л	0 0л	0 0л

Чтобы х⁰ = (0; 0; 35/6; 19/2; 32/3) = (0; 0; 5 ; 9,5; 10) был оптимальным планом, необходимо и достаточно выполнения следующих условий:

,

Система не имеет решений.

Зафиксируем значение л: лф = 0. Тогда на второй итерации в базис будет вводиться А₂, выводиться - А₅.

Таблица 6 Решение основной задачи

	14	19	23	0	0
	-л	л	2л	0л	0л
Су?	Су??	Базис	А0=b	А1	А2	А3	А4	А5
0 19 23	0л л 2л	А4 А2 <А3	9,5 16 1/2	-1/2v 0 1/2	0 1 0	0 0 1	1 0 0	0 3/2 -1/2
		С(х)/ ?j? С(х)/ ?j??	315,5 17л	-5/2 2л	0 0л	0 0л	0 0л	17 1/2л

Чтобы х¹ = (0;16; Ѕ; 9,5; 0) был оптимальным планом, необходимо и достаточно выполнения следующих условий:

=> л ? 5/4 ? 1

То есть, при л ? [1 ; +?) оптимальный план х¹ = (0;16; Ѕ; 9,5) и значение целевой функции С (х¹) = 315,5 +17л.

Проанализируем ситуацию, когда л < 5/4, тогда неравенство -5/2 +2л ? 0 перестанет выполняться, тогда А₁ станет отрицательной и будет вводиться в базис.

Таблица 7 Решение основной задачи

	14	19	23	0	0
	-л	л	2л	0л	0л
Су?	Су??	Базис	А0=b	А1	А2	А3	А4	А5
0 19 14	0л л -л	А4 <А2 А1	10 16 1	0 0 1	0 1 0	1 0 2	1 0 0	-1/2v 3/2 -1
		С(х)/ ?j? С(х)/ ?j??	318 15л	0 0л	0 0л	5 -4л	0 0л	29/2 5/2л

Чтобы х² = (1;16; 0; 10; 0) был оптимальным планом, необходимо и достаточно выполнения следующих условий:

=> -5 л < 1

При л ? [-5 ; 1 ) оптимальный план х² = (1;16; 0; 10; 0) и значение целевой функции С(х²) = 318 + 15л.

Если л < -5 , то неравенство 29/2 - 5/2л ? 0 перестанет выполняться, тогда А5 станет отрицательной и будет вводиться в базис.

Таблица 8 Решение основной задачи

	14	19	23	0	0
	-л	л	2л	0л	0л
Су?	Су??	Базис	А0=b	А1	А2	А3	А4	А5
0 0 14	0л 0л -л	А4 А5 А1	46/3 32/3 35/3	0 0 1	1/3 2/3 2/3	1 0 2	1 0 0	0 1 0
		С(х)/ ?j? С(х)/ ?j??	490/3 -35/3л	0 0л	-29/3 -5/3л	5 -4л	0 0л	0 0л

Чтобы х³ = (35/3; 0; 0; 46/3; 32/3) = ( 11 ; 0;0; 15 ; 10 ) был оптимальным планом, необходимо и достаточно выполнения следующих условий:

=> л < -5

При л ? ( - ?; -5 ) оптимальный план х³ = ( 11 ; 0;0; 15 ; 10 ) и значение целевой функции С (х³) = 163 - 11 л.

Ответ: Для всех значений параметра -? < л < +? найдены оптимальные планы и значения целевой функции

1. л ? [1 ; +?), х^1* = (0;16; Ѕ; 9,5), С (х^1*) = 315,5 +17л.

2. л ? [-5 ; 1 ), х^2* = (1;16; 0; 10; 0), С(х^2*) = 318 + 15л.

3. л ? ( - ?; -5 ), х^3* = ( 11 ; 0;0; 15 ; 10 ), С (х³*) = 163 - 11 л.

Предприятие может использовать не более чем 27 +2м единиц ресурса R₁ и не более чем 34-м единиц ресурса R₂, где м - некоторый параметр. Для каждого возможного значения м определить план производства изделий, при котором выручка от реализации является максимальной.

Решение:

х₁ - количество продукции А;

х₂ - количество продукции В;

х₃ - количество продукции С.

Целевая функция выглядит следующим образом:

С₁(х) = 14х₁+19х₂+23х₃ > max

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

,

Запишем задачу в канонической форме:

,

В задаче отсутствует единичный базис. Применим метод искусственного базиса.

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

() = -х₆ > max

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

,

БДП вспомогательной задачи: = (0;0;0;27;34;35). Симплекс-таблица для вспомогательной задачи представлена в таблице 2:

Таблица 9 Решение вспомогательной задачи

	0	0	0	0	0	-1
Су	Базис	А0=b	А1	А2	А3	А4	А5	А6
0 0 -1	А4 А5 <А6	27 34 35	2м -м 0м	1 2 3	1 2 2	3v 4 6	1 0 0	0 1 0	0 0 1
	()/?j	-35	0м	-3	-2	-6	0	0	0
0 0 0	А4 А5 А3	19/2 32/3 35/6	2м -м 0м	-1/2 0 1/2	0 2/3 1/3	0 0 1	1 0 0	0 1 0	Ѕ 2/3 1/6
	()/?j	0	0м	0	0	0	0	0	1

На второй итерации получен оптимальный план вспомогательной задачи: х⁰ = (0; 0; 35/6; 19/2; 32/3), о чем свидетельствуют неотрицательные двойственные оценки и отсутствие отрицательных компонент в столбце А₀.

Оптимальный план вспомогательной задачи будет использоваться как начальное БДП для основной задачи. Для этого пересчитаем двойственные оценки основной задачи, используя начальный БДП х⁰ = (0; 0; 35/6; 19/2; 32/3).

Таблица 10 Решение основной ЗЛПП

	12	16	17	0	0
Су	Базис	А0=b	А1	А2	А3	А4	А5
0 0 0	А4 <А5 А3	19/2 32/3 35/6	2м -м 0м	-1/2 0 1/2	0v 2/3 1/3	0 0 1	1 0 0	0 1 0
	С(х)/ ?j	805/6	0м	-5/2	-34/3	0	0	0
0 19 23	А4 А2 <А3	19/2 16 1/2	2м -3/2м 1/2м	-1/2v 0 1/2	0 1 0	0 0 1	1 0 0	0 3/2 -1/2
	С(х)/ ?j	631/2	-17м	-5/2	0	0	0	17
0 19 14	А4 А2 <А1	10 16 1	5/2м -3/2м м	0 0 1	0 1 0	1 0 2	1 0 0	-1/2v 3/2 -1
	С(х)/ ?j	318	-14,5м	0	0	5	0	29/2

На первой итерации есть отрицательные двойственные оценки, наименьшая из них -34/3, поэтому столбец А₂ вводится в базис. На второй итерации есть отрицательная двойственная оценка -5/2, поэтому столбец А₁ вводится в базис. При пересчете таблицы получен БДП х² = ( 1+м; 16 - 1,5 м; 0; 10 + 2,5м)

Чтобы БДП х² был оптимальным, необходимо, чтобы все двойственные оценки компоненты в А₀ были неотрицательны:

=> 1 ? м ? 10

При м ? [1; 10 ] оптимальный план х² = ( 1+м; 16 - 1,5 м; 0; 10 + 2,5м) и значение целевой функции С(х²) = 318 - 14,5м.

Проанализируем ситуацию, когда м > 10 , тогда неравенство 16 - 3/2м ? 0 перестанет выполняться, то есть в А₀ появится отрицательная компонента, будет применяться двойственный симплекс-метод. Но при м > 10 задача не имеет решения.

Проанализируем случай, когда м < 1, тогда А1 станет отрицательной и будет выводиться из базиса, применим двойственный симплекс-метод.

Таблица 11 Решение основной ЗЛПП

	12	16	17	0	0
Су	Базис	А0=b	А1	А2	А3	А4	А5
0 19 0	<А4 А2 А5	19/2 35/2 -1	2м 0м -1м	-1/2v 3/2 -1	0 1 0	0 3 2	1 0 0	0 0 1
	С(х)/ ?j	665/2	0м	29/2	0	34	0	0

Чтобы х3 = (0, 35/2; 0; 19/2 +2м; -1-м) = (0; 17,5; 0; 9,5 +2м; -1-м) был оптимальным планом, необходимо, чтобы все двойственные оценки компоненты в А₀ были неотрицательны:

=> -4.75 ? м < -1

При м ? [-4,75; -1) оптимальный план х3 = (0; 17,5; 0; 9,5 +2м; -1-м) и значение целевой функции С(х³) = 332,5

Проанализируем ситуацию, когда м < - 4,75, тогда А₄ станет отрицательной и будет выводиться из базиса, применим двойственный симплекс-метод.

Таблица 12 Решение основной ЗЛПП

	12	16	17	0	0
Су	Базис	А0=b	А1	А2	А3	А4	А5
14 19 0	А1 А2 А5	-19 46 -20	-4м 6м -5м	1 0 0	0 1 0	0 3 2	-2 3 -2	0 0 1
	С(х)/ ?j	608	58м	0	0	34	29	0

Чтобы х⁴ = (-19 - 4м; 46+ 6м; 0; 0; -20 - 5м) был оптимальным планом, необходимо, чтобы все двойственные оценки компоненты в А₀ были неотрицательны:

=> -7 ? м < -4,75

При м ? [-7 ; -4,75) оптимальный план х⁴ = (-19 - 4м; 46+ 6м; 0; 0; -20 - 5м) и значение целевой функции С(х⁴) = 608 + 58м.

Проанализируем случай, когда м < -7 , тогда неравенство 46 + 6м ? 0 перестанет выполняться, то есть в А₀ появится отрицательная компонента, будет применяться двойственный симплекс-метод. Но при м < -7 задача не имеет решения.

Ответ: Для всех значений параметра -? < м < +? найдены оптимальные планы и целевые функции:

1. м ? [1; 10 ], х^2* = ( 1+м; 16 - 1,5 м; 0; 10 + 2,5м), С(х^2*) = 318 - 14,5м.

2. м ? (10 ; +?) задача не имеет решения.

3. м ? [-4,75; -1), х3* = (0; 17,5; 0; 9,5 +2м; -1-м), С(х^3*) = 332,5.

4. м ? [-7 ; -4,75), х^4* = (-19 - 4м; 46+ 6м; 0; 0; -20 - 5м) , С(х^4*) = 608 + 58м.

5. м ? (-?; -7 ) задача не имеет решения.

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

...