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

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

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

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

 

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

 

 

 

 

 

 

 

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

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

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

 

 

 

 

 

 

Выполнил: студент гр. ЭЗ-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