Математические модели и методы в управлении

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ

 РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

 

Курганский Государственный Университет

 

 

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

по дисциплине

«Математические модели и методы в  управлении»

 

 

 

 

 

 

Выполнил: студент гр. ЭЗ-5726 Предеин А.А.

                                                                                

Преподаватель: Хмелева  Ф.Г.

                                                                                                     

 

 

 

 

 

 

 

                                                  

 

 

 

 

 

 

2011

 

 

Содержание:

Задача 1…………………………………………………………………………..3

Задача 2…………………………………………………………………………..8

Задача 3…………………………………………………………………………10

Задача 4 …………………………………………………………………………19

Задача 5………………………………………………………………………….21

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 1

Задачу линейного  программирования

F(х₁; х₂) = 2х₁ - х₂ → min

                         х₁ +х₂ ≥4,

                          –х₁ +2 х₂ ≤ 2,

                         х₁ + 2х₂ ≤ 10,

                         х₁≥ 0, х₂ ≥ 0

 

а) Решить геометрически:

• Изобразить множество допустимых планов
• Указать оптимальное решение (х₁; х₂), максимальное значение целевой функции.

б) Привести к каноническому  виду.

в) Найти оптимальное  решение задачи линейного программирования симплексным методом.

Решение:

а) Решим геометрически:

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

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

Построим область решений  первого неравенства системы  ограничений 

х₁ + х₂ ≥ 4.     

Сначала построим прямую, заданную уравнением х₁ + х₂ = 4, которая на рисунке 1 обозначена . Для этого вычислим координаты точек пересечения этой прямой с осями координат

 

х₁ = 0,                  х₁ = 4,

х₂ = 4                   х₂ = 0.

Рисунок 1 – График решения  задачи     

 

Для определения полуплоскости  решений нашего неравенства возьмем  произвольную точку плоскости, не лежащую на прямой х₁ +х₂ = 4, например (0; 0) и подставим ее координаты в неравенство 0 + 0 ≥ 4. В результате подстановки мы получили неверное числовое неравенство 0 ≥4, а это означает, что начало координат не лежит в полуплоскости решений нашего неравенства. Поэтому мы  заштрихуем полуплоскость, в которой начало координат не лежит (см. рис. 1).

Аналогично строим полуплоскости  решений остальных неравенств системы  ограничений, каждый раз заштриховывая  «нужную» полуплоскость (прямые  -х₁ +2х₂ = 2 и х₁ + 2х₂ = 10 обозначены ‚ и ƒ).

Для этого вычислим координаты точек  пересечения этих прямых с осями  координат

(2)                                 (3)                                                                               

   х₁ = 0,      х₁ = -2,          х₁ = 0,          х₁ = 10,           

   х₂ = 1,       х₂ = 0,           х₂ = 5,          х₂ = 0.     

                                

        Левая и  нижняя полуплоскости вычеркиваются  по смыслу последних неравенств (х₁ ≥ 0 и х₂ ≥ 0).

 Общая заштрихованная  часть плоскости и представляет  собой искомую область решений  задачи – это четырехугольник  АВСD (см. рис. 1).

Теперь нужно среди  точек область решений найти  такую, в которой целевая функция F(х₁; х₂) = 2х₁ - х₂ достигает минимального значения. Для этого построим прямую, заданную уравнением 2х₁ - х₂ = 0. Которая является линией нулевого уровня функции F(х₁; х₂). Как известно, линии уровней линейной функции образуют на плоскости семейство параллельных прямых, на каждой из которых функция принимает постоянное значение. При переходе от одной линии уровня к другой значение функции изменяется.

Направление возрастания линейной функции F(х₁; х₂) = 2х₁ - х₂ указывает вектор с началом в точке О (0; 0) и концом в точке М(2; -1), координаты которой равны коэффициентам при соответствующих переменных функции F.

 Для нахождения минимального  решения нужно «передвигать»  линию нулевого уровня функции  F параллельно самой себе в направлении, указанном построенным вектором, до точки ее «первой встречи» с областью решения, которая и является максимальным значением задачи. В нашем случае это точка А точка пересечения прямых  и ‚. Координаты (х₁^*; х₂^*) точки А найдем, решив систему уравнений:

                                    х₁^* + х₂^* = 4,

                                  -х₁^* + 2х₂^* = 2                   откуда х₁^* = 2, х₂^* = 2

F(А) = F^*(2; 2) = 2·2 - 1·2 = 2. Это минимальное значение функции на рассматриваемой области решений.

         Ответ: минимальное значение функции  равно 2.

        б) Запишем каноническую форму:

 F(х) = 2х₁- х₂  ® min.

        -х₁  - х₂ +х₃ =  -4,

   -х₁ + 2х₂ +х₄ =  2,

      х₁ + 2х₂  +х₅ =  10,                                             

х₁ ³ 0, х₂ ³ 0.

в) Решим задачу симплекс- методом;

Шаг 1:

Базисные  переменные	Переменные					Свободный член	Оценочное отношение
	х1	х2	х3	х4	х5
х3	-1	-1	1	0	0	-4
х4	-1	2	0	1	0	2
х5	1	2	0	0	1	10
F(х)	2	-1	0	0	0	0

 

Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный  член (-4). Ведущая строка - х₃. В строке х₃ так же найдем максимальный по модулю отрицательный свободный член (-1). Столбец х₁- ведущий. Пересчитаем таблицу.

Шаг 2:

Базисные  переменные	Переменные					Свободный член	Оценочное отношение
	х1	х2	х3	х4	х5
х1	1	1	-1	0	0	4
х4	0	3	-1	1	0	6
х5	0	1	1	0	1	6
F(х)	0	-3	2	0	0	-8

 

Шаг 3:

Базисные  переменные	Переменные					Свободный член	Оценочное отношение
	х1	х2	х3	х4	х5
х1	1	1	-1	0	0	4
х4	0	3	-1	1	0	6
х5	0	1	1	0	1	6
F(х)	0	-3	2	0	0	-8

 

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

Шаг 4:

Базисные  переменные	Переменные					Свободный член	Оценочное отношение
	х1	х2	х3	х4	х5
х1	1	0	-2/3	-1/3	0	2
х2	0	1	-1/3	1/3	0	2
х5	0	0	4/3	-1/3	1	4
F(х)	0	0	1	1	0	-2

 

Найдено оптимальное  решение

 

         Ответ: минимальное значение функции  равно 2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 2

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

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

Ресурсы	Ореховый звон	Райский вкус	Батончики	Белка	Ромашка	ограничения
Темный шоколад	0,8	0,5	1	2	1,1	1411
Светлый шоколад	0,2	0,1	0,1	0,1	0,2	149
Сахар	0,3	0,4	0,6	1,3	0,05	815,5
Карамель	0,2	0,3	0,3	0,7	0,5	466
Орехи	0,7	0,1	0,9	1,5	0	1080
Прибыль	1	0,7	1,1	2	0,6

 

А) Каков должен быть оптимальный  производственный план?

Б) Все ли виды продуктов  выгодно производить?

Решение:

Для построения математической модели необходимо ответить на следующие  три вопроса:

1) Как идентифицировать искомые величины, т.е. переменные этой задачи?

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

3) Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, описанные задаче?

Переменные

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

х₁ - ореховый звон;

х₂ - райский вкус;

х₃ - батончик;

х₄ – белка;

х₅ – ромашка.

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

В условии  задачи сформулирована цель, добиться максимального дохода от реализации продукции. Прибыль от реализации каждого типа продуктов соответственно равна 1; 0,7; 1,1; 2 и 0,6.

Поэтому целевой функцией (ЦФ) будет математическое выражение, в котором суммируется доход  от продажи  продуктов.

L(Х) = х₁ + 0,7х₂ + 1,1х₃ + 2х₄ + 0,6х₅ ® mах.

Ограничения

Ограничения, налагаемые на возможные объемы выпуска продукции, т.е. на переменные х₁, х_2, х₃, х₄ и х₅, обуславливаются:

- количеством  расходуемого сырья;

Ограничения на расход сырья можно записать в виде:

  Расход конкретного вида  сырья     ≤    Максимально  возможный запас     

                    на изделия                                          данного сырья 

 

а математически – в виде:

0,8х₁ + 0,5х₂ +  х₃  +  2х₄  +  1,1х₅  ≤ 1411;

0,2х₁ + 0,1х₂ +  0,1х₃  +  0,1х₄  +  0,21х₅  ≤ 149;

0,3х₁ + 0,4х₂ +  0,6х₃  +  1,3х₄  + 0,05х₅  ≤ 815,5;

0,2х₁ + 0,3х₂ +  0,3х₃  +  0,7х₄  +  0,5х₅  ≤ 466;

0,7х₁ + 0,1х₂ +  0,9х₃  +  1,5х₄  ≤ 1080;

 

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

х₁ ³ 0, х₂ ³ 0, х₃ ³ 0, х₄ ³ 0, х₅ ³ 0

Таким образом, математическая модель этой задачи имеет  вид

L(Х) = х₁ + 0,7х₂ + 1,1х₃ + 2х₄ + 0,6х₅ ® mах.

 

      0,8х₁ + 0,5х₂ +  х₃  +  2х₄  +  1,1х₅  ≤ 1411;

              0,2х₁ + 0,1х₂ +  0,1х₃  +  0,1х₄  +  0,21х₅  ≤ 149;

                 0,3х₁ + 0,4х₂ +  0,6х₃  +  1,3х₄  +  0,05х₅  ≤ 815,5;

             0,2х₁ + 0,3х₂ +  0,3х₃  +  0,7х₄  +  0,5х₅  ≤ 466;

0,7х₁ + 0,1х₂ +  0,9х₃  +  1,5х₄  ≤ 1080;

х₁ ³ 0, х₂ ³ 0, х₃ ³ 0, х₄ ³ 0, х₅ ³ 0.

 

Решим задачу симплекс-методом  средствами Excel.

переменная Х1	450
переменная Х2	60
переменная Х3	10
переменная Х4	500
переменная Х5	10
Функция	1509
Ограничения 1	1411	1411
ограничения 2	149	149
ограничения 3	815,5	815,5
ограничения 4	466	466
ограничения 5	1080	1080

 

Итак, необходимо произвести ореховый звон в количестве 450, райский вкус – 60, батончики – 10, белка – 500, ромашка - 10.  Прибыль фабрики от их реализации будет максимальной и составляет 1509 ден. ед.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 3

Решить транспортную задачу

Составить экономико-математическую модель транспортной задачи. Найти оптимальное распределение поставок и минимальные затраты на перевозку, выполнив первоначальное распределение поставок методом «северо-западного» угла. 

Таблица 1 – Исходная транспортная таблица

Пункты отправления, Аi	Пункты потребления, Bj			Запасы (ед. товара)
	В1	В2	В3
А1	2	2	3	50
А2	2	4	5	70
А3	6	5	7	60
Потребность (ед. товара)	60	60	50	170 ≠180

 

Решение:

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

 

                               потребности                запасы                   

 

                              60 + 60 + 50   <   50 + 70 + 60

 

                                170 ед. товара            180 ед. товара

Для того, чтобы сбалансировать данную задачу введем фиктивный пункт  потребления А_ф с фиктивным потребностями 10 (ед. товара) и фиктивным тарифом 100 (р./ед. товара) (таблица 2).

 

 

 

Таблица 2 – Сбалансированная транспортная таблица

Пункты отправления, Аi	Пункты потребления, Bj				Запасы (ед. товара)
	В1	В2	В3	В4
А1	2	2	3	100	50
А2	2	4	5	100	70
А3	6	5	7	100	60
Потребность (ед. товара)	60	60	50	10	180 =180

 

Составление плана перевозок. Метод «северо-западного угла».

50	-	-	-
				70
				60
10	60	50	10

 

Рисунок 2

Заполним клетку а₁₁ – «северо-западный угол» матрицы перевозок. В нее можно запланировать перевозку 50 единиц груза: возможности поставщика А₁ полностью исчерпаны, и  потребителю В₁ необходимо еще поставить 10 ед товара. При этом первая строка матрицы перевозок будут закрыта – рисунок 2.

Заполняем «северо-западный угол» оставшейся незаполненной  части таблицы – клетку а_21. В нее можно запланировать перевозку 10 единиц груза,  у  поставщика  А₂, потребителю В₁ заказ выполнен полностью; но при этом остается еще 60 единиц груза возможность поставщика А₂; при этом 1-й столбец матрицы перевозок закрыт – рисунок 3.

50	-	-	-
10				60
-				60
	60	50	10

 

Рисунок 3

Снова заполняем   «северо-западный угол» незаполненной части таблицы  –  клетка   а₂₂. В нее можно запланировать перевозку 60 единиц груза, имеющихся у А₂, потребителю В₂; при этом возможности поставщика А₂ исчерпаны полностью; при этом вторая строка и второй столбец матрицы перевозок будут закрыты – рисунок 4. Так как закрылись одновременно строка и столбец, ведем фиктивную нулевую перевозку клетка а₃₂ – рисунок 4.

50	-	-	-
10	60	-	-
-	0ф			60
		50	10

 

Рисунок 4

В оставшейся незаполненной  части матрицы  перевозок заполняем сначала «северо-западный угол» - клетку а₃₃, а₃₄ (в них ставим 50 и 10 единиц груза соответственно и закрываем 3-й и 3-й столбцы матрицы); получаем план перевозок – рисунок 5. 

 

50	-	-	-
10	60	-	-
-	0ф	50	10

 

Рисунок 5

 

Таким образом, опорный  план, найденный методом Северо-Западного  Угла имеет вид

                                   50    0      0      0                                   

                  Х_СЗУ =      10    60    0      0           (ед. товара).

                                      0      0^ф   50   10^Ф

                                     

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

 L(Х_СЗУ) = 50·2 + 10·2 + 60·4 + 50·7  = 710 (ден.ед.)

В нашем случае получилась вырожденная задача, так как была необходимость одновременного закрытия столбца и строки, поэтому приходится вводить фиктивную нулевую перевозку, чтобы соблюсти указанный принцип для невырожденных задач, заполненные  число клеток  равно, как известно из теории, т+п-1 где т и п -размеры матрицы перевозок. В нашем случае т = 4, n = 3 , поэтому должны быть заполнены 4 + 3 — 1 = 6 клеток, что и получилось.

б) Метод наименьшей стоимости.

 Находим клетку  матрицы перевозок с наименьшими  тарифами; клетка а₂₁в нее помещаем 60 единиц,   и закрываем  первый столбец,  а у поставщика А₂ оставляем 70 – 60 = 10 единиц груза. Получаем рисунок 6. В оставшейся незаполненной части матрицы перевозок наименьший тариф имеет клетка  а₁₂.  Заполняем ее: ставим перевозку 50,  закрываем первую строку,  а потребителя В1₂ остается  еще 10 единиц груза, рисунок 7.   

-				50
60				10
-				60
	60	50	10
-	50	-	-
60				10
-				60
	10	50	10