Контрольная работа по «Методы оптимальных решений»

 

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Владимирский государственный университет

имени Александра Григорьевича и Николая Григорьевича Столетовых»

(ВлГУ)

Кафедра «Бизнес-экономика и информатика» 

 

 

 

Контрольная работа

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

«Методы оптимальных решений»

Вариант №7 

 

Выполнил:

ст.гр ЗЭКвд-114

Симакова А.Н

 Принял:

преподаватель

 Крашенинникова О.В.

 

 

 

Владимир 2015

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

z= x1-x2 → max

Решение.

Необходимо найти максимальное значение целевой функции z= x1-x2 → max, при системе ограничений:

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

Построим уравнение x1+x2 = 2 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 2. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 2. Соединяем точку (0;2) с (2;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 1 • 0 - 2 ≤ 0, т.е. x1+x2 - 2≤ 0 в полуплоскости ниже прямой.

Построим уравнение x1+x2 = 1 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 1. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 1. Соединяем точку (0;1) с (1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 1 • 0 - 1 ≤ 0, т.е. x1+x2 - 1≥ 0 в полуплоскости выше прямой.

Построим уравнение 2x1-x2 = 2 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = -2. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 1. Соединяем точку (0;-2) с (1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 2 • 0 - 1 • 0 - 2 ≤ 0, т.е. 2x1-x2 - 2≤ 0 в полуплоскости ниже прямой.

Построим уравнение 2x1-x2 = 1 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = -1. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 0.5. Соединяем точку (0;-1) с (0.5;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 2 • 0 - 1 • 0 - 1 ≤ 0, т.е. 2x1-x2 - 1≥ 0 в полуплоскости выше прямой.

 

Границы области допустимых решений

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

Обозначим границы области многоугольника решений.

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

Построим прямую, отвечающую значению функции z = 0: z = x1-x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации Z(x). Начало вектора – точка (0; 0), конец – точка (1; -1). Будем двигать эту прямую параллельным образом. На графике эта прямая обозначена пунктирной линией.

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

x2=0

2x1-x2=2

Решив систему уравнений, получим: x1 = 1, x2 = 0

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

Z (x) = 1*1 - 1*0 = 1

 

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

z= 10x1+14x2 +12 x3→ max

 

Решение.

Определим максимальное значение целевой функции z(x) = 10x1 + 14x2 + 12x3 при следующих условиях - ограничений.

2x1 + 4x2 + 5x3≤120

x1 + 8x2 + 6x3≤280

7x1 + 4x2 + 5x3≤240

4x1 + 6x2 + 7x3≤360

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных. В 1-м неравенстве  вводим базисную переменную x4. В 2-м неравенстве вводим базисную переменную x5. В 3-м неравенстве вводим базисную переменную x6. В 4-м неравенстве вводим базисную переменную x7. 

2x1 + 4x2 + 5x3 + 1x4 + 0x5 + 0x6 + 0x7 = 120

1x1 + 8x2 + 6x3 + 0x4 + 1x5 + 0x6 + 0x7 = 280

7x1 + 4x2 + 5x3 + 0x4 + 0x5 + 1x6 + 0x7 = 240

4x1 + 6x2 + 7x3 + 0x4 + 0x5 + 0x6 + 1x7 = 360

 

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

 

2	4	5	1	0	0	0
1	8	6	0	1	0	0
7	4	5	0	0	1	0
4	6	7	0	0	0	1

 

Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,120,280,240,360)

Базисное решение называется допустимым, если оно неотрицательно.

 

Базис	B	x1	x2	x3	x4	x5	x6	x7
x4	120	2	4	5	1	0	0	0
x5	280	1	8	6	0	1	0	0
x6	240	7	4	5	0	0	1	0
x7	360	4	6	7	0	0	0	1
z(x0)	0	-10	-14	-12	0	0	0	0

Переходим к основному алгоритму симплекс-метода.

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

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение  новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

3. Определение  новой свободной переменной.

Вычислим значения Di по строкам, как частное от деления

и из них выберем наименьшее:

min (120 : 4 , 280 : 8 , 240 : 4 , 360 : 6 ) = 30

Следовательно, 1-ая строка является ведущей.

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x4	120	2	4	5	1	0	0	0	30
x5	280	1	8	6	0	1	0	0	35
x6	240	7	4	5	0	0	1	0	60
x7	360	4	6	7	0	0	0	1	60
z(x1)	0	-10	-14	-12	0	0	0	0	0

4. Пересчет симплекс-таблицы.

Вместо переменной x4 в план 1 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент 4

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x2 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
120 : 4	2 : 4	4 : 4	5 : 4	1 : 4	0 : 4	0 : 4	0 : 4
280-(120 • 8):4	1-(2 • 8):4	8-(4 • 8):4	6-(5 • 8):4	0-(1 • 8):4	1-(0 • 8):4	0-(0 • 8):4	0-(0 • 8):4
240-(120 • 4):4	7-(2 • 4):4	4-(4 • 4):4	5-(5 • 4):4	0-(1 • 4):4	0-(0 • 4):4	1-(0 • 4):4	0-(0 • 4):4
360-(120 • 6):4	4-(2 • 6):4	6-(4 • 6):4	7-(5 • 6):4	0-(1 • 6):4	0-(0 • 6):4	0-(0 • 6):4	1-(0 • 6):4
0-(120 • -14):4	-10-(2 • -14):4	-14-(4 • -14):4	-12-(5 • -14):4	0-(1 • -14):4	0-(0 • -14):4	0-(0 • -14):4	0-(0 • -14):4

Представим расчет каждого элемента в виде таблицы:

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x2	30	1/2	1	5/4	1/4	0	0	0
x5	40	-3	0	-4	-2	1	0	0
x6	120	5	0	0	-1	0	1	0
x7	180	1	0	-1/2	-3/2	0	0	1
F(X1)	420	-3	0	11/2	7/2	0	0	0

 

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

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение  новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

3. Определение  новой свободной переменной.

Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

min (30 : 1/2 , - , 120 : 5 , 180 : 1 ) = 24

Следовательно, 3-ая строка является ведущей.

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x2	30	1/2	1	11/4	1/4	0	0	0	60
x5	40	-3	0	-4	-2	1	0	0	-
x6	120	5	0	0	-1	0	1	0	24
x7	180	1	0	-1/2	-11/2	0	0	1	180
F(X2)	420	-3	0	51/2	31/2	0	0	0	0