Контрольная работа на тему Контрольная работа 161230-02

Содержание


Задача 1 3
Задача 2 27
Список используемой литературы 44



Задача 1
Ниже приведены комплексные задачи линейного программирования. Необходимо выполнить в указанном порядке следующие задания.
1. Найти оптимальный план прямой задачи графическим методом.
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план прямой задачи с применением функции поиска решения в Excel.
5. Дать интерпретацию изменения решения (по отчету на устойчивость) при условии изменения коэффициентов целевой функции на (1/3)% и (1/2)% соответственно.
6. Показать изменения оптимального плана при изменении правой части первого из ограничений задачи в системе уравнений на 6%. Сравнить результаты с результатом, полученный графическим методом (см. п.1).
7. Найти наиболее дефицитные ресурсы и показать возможности повышения дохода предприятия путем увеличения запаса дефицитного ресурса. Обосновать свой выбор по отчету на устойчивость из п.5.


Решение
1. Найти оптимальный план прямой задачи графическим методом.
Найти наибольшее значение функции
F = – 4 x1 + 7 x2
при следующих ограничениях:



3 x1
+
4 x2
?
9



– 2 x1
+
x2
?
5



11 x1
+
7 x2
?
72



– x1
+
18 x2
?
13


x1 ? 0 x2 ? 0
Точки, координаты которых удовлетворяют одновременно всем неравенствам системы ограничений, называются областью допустимых решений.
Очевидно, для нахождения области допустимых решений данной задачи, необходимо последовательно рассмотреть каждое неравенство. (см. шаг 1 – шаг 4)
Последние два шага (см. шаг 5 – шаг 6) служат непосредственно для получения ответа.
Это стандартная схема решения. Если область допустимых решений представляет собой точку или пустое множество, то решение будет короче.
Подставив координаты любой точки A (x1, x2), принадлежащей области допустимых решений, в выражение функции F, можно получить значение функции в данной точке F(A).
По условию задачи: x1 ? 0 x2 ? 0.
Если бы это было единственным условием, то область допустимых решений имела бы вид, как на рисунке справа (вся первая четверть).


Рисунок 1 – Начало построения
Шаг №1. Рассмотрим неравенство 1 системы ограничений.
3 x1 + 4 x2 ? 9
Построим прямую: 3 x1 + 4 x2 = 9
Пусть x1 =0 => 4 x2 = 9 => x2 = 9/4
Пусть x2 =0 => 3 x1 = 9 => x1 = 3
Найдены коородинаты двух точек (0, 9/4) и (3,0). Соединяем их и получаем необходимую прямую (1). Возникает вопрос, нас интересуют точки расположенные выше или ниже построенной прямой (1) Вернемся к исходному неравенству.
3 x1 + 4 x2 ? 9
Перенесем все в правую часть неравенства, оставив в левой части только x2
4 x2 ? – 3 x1 + 9
x2 ? – 3/4 x1 + 9/4
Знак неравенства ?, следовательно, нас интересуют точки расположенные выше построенной прямой (1).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке справа.


Рисунок 2 – Шаг №1
Шаг №2. Рассмотрим неравенство 2 системы ограничений.
– 2 x1 + x2 ? 5
Построим прямую: – 2 x1 + x2 = 5
Пусть x1 =0 => x2 = 5
Пусть x2 =0 => – 2 x1 = 5 => x1 = -5/2
Найдены коородинаты двух точек (0, 5) и (-5/2,0). Соединяем их и получаем необходимую прямую (2).
Возникает вопрос, нас интересуют точки расположенные выше или ниже построенной прямой (2). Вернемся к исходному неравенству.
– 2 x1 + x2 ? 5
Перенесем все в правую часть неравенства, оставив в левой части только x2: x2 ? 2 x1 + 5
Знак неравенства ?, следовательно, нас интересуют точки расположенные ниже построенной прямой (2). Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке справа.


Рисунок 3 – Шаг №2

Шаг №3. Рассмотрим неравенство 3 системы ограничений.
11 x1 + 7 x2 ? 72
Построим прямую: 11 x1 + 7 x2 = 72
Пусть x1 =0 => 7 x2 = 72 => x2 = 72/7
Пусть x2 =0 => 11 x1 = 72 => x1 = 72/11
Найдены коородинаты двух точек (0, 72/7) и (72/11,0). Соединяем их и получаем необходимую прямую (3). Возникает вопрос, нас интересуют точки расположенные выше или ниже построенной прямой (3). Вернемся к исходному неравенству. 11 x1 + 7 x2 ? 72
Перенесем все в правую часть неравенства, оставив в левой части только x2: 7 x2 ? – 11 x1 + 72
x2 ? – 11/7 x1 + 72/7
Знак неравенства ?, следовательно, нас интересуют точки расположенные ниже построенной прямой (3). Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке справа.


Рисунок 4 – Шаг №3

Шаг №4. Рассмотрим неравенство 4 системы ограничений.
– x1 + 18 x2 ? 13
Построим прямую: – x1 + 18 x2 = 13
Пусть x1 =0 => 18 x2 = 13 => x2 = 13/18
Пусть x2 =0 => – x1 = 13 => x1 = -13
Найдены коородинаты двух точек (0, 13/18) и (-13,0). Соединяем их и получаем необходимую прямую (4). Возникает вопрос, нас интересуют точки расположенные выше или ниже построенной прямой (4) ? Вернемся к исходному неравенству. – x1 + 18 x2 ? 13
Перенесем все в правую часть неравенства, оставив в левой части только x2: 18 x2 ? x1 + 13
x2 ? 1/18 x1 + 13/18
Знак неравенства ?, следовательно, нас интересуют точки расположенные выше построенной прямой (4).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке справа.


Рисунок 5 – Шаг №4
Шаг №5. Строим вектор C = (-4, 7), координатами которого являются коэффициенты функции F.


Рисунок 6 – Шаг №5
Шаг №6. Будем перемещать «красную» прямую, перпендикулярно вектору C, от правого нижнего угла к левому верхнему.
В точке, в которой «красная» прямая в первый раз пересечет область допустимых решений, функция F достигает своего наименьшего значения.
В точке, в которой «красная» прямая в последний раз пересечет область допустимых решений, функция F достигает своего наибольшего значения. Функция F достигает наибольшего значения в точке A. (см. рисунок справа) Точка A одновременно принадлежит прямым (2) и (3). Составим систему уравнений:



– 2 x1
+
x2
=
5
 =>
x1 = 37/25



11 x1
+
7 x2
=
72

x2 = 199/25

Вычислим значение функции F в точке A (37/25,199/25).
F (A) = -4 * 37/25 + 7 * 199/25 = 249/5


Рисунок 7 – Шаг №6
Ответ:
x1 = 37/25
x2 = 199/25
F max = 249/5
Замечание: если возникли сомнения, что в точке А функция F достигает своего максимума, необходимо найти значение функции в интересующей точке и сравнить с F(A).
2. Построить двойственную задачу. Двойственная задача
Прямая задача линейного программирования имеет вид:
F(X)=-4X1+7X2 (max)
Ограничения:
3X1
+
4X2

?
9

-2X1
+
1X2

?
5

11X1
+
7X2

?
72

-1X1
+
18X2

?
13

X1
?
0

X2
?
0

Так как в прямой задаче требуется найти максимум фунции, то приведем пе