Линейное программирование

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное автономное образовательное учреждение высшего образования

КАФЕДРА СИСТЕМНОГО АНАЛИЗА И ЛОГИСТИКИ

ОТЧЕТ
ЗАЩИЩЕН С ОЦЕНКОЙ

ПРЕПОДАВАТЕЛЬ

РАБОТУ ВЫПОЛНИЛ

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

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

z = -x1+x2max[pic 1]

-x1+4x2 9[pic 2]

3x1+x2[pic 3]

x1+2x2  ≤ 7

5x1-8x2 -1[pic 4]

x1, x2  0[pic 5]

Решение:

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

[pic 6]

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

Обозначим границы области допустимых решений.[pic 7]

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

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

[pic 8]

Прямая целевой функции пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (2), то ее координаты вычисляются с помощью  системы уравнений этих прямых:

-x1+4x2=9

3x1+x2=5

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

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

F(А) = -1*0.8462 + 1*2.4615 = 1.6154

2. Анализ чувствительности

2.1 На сколько можно увеличить (уменьшить) дефицитные ресурсы для улучшения оптимального решения?

Связывающим ограничениям (1) и (2)  соответствуют дефицитные ресурсы.

Определим на сколько можно увеличить ресурс соответствующий (1) ограничению.

Перемещая прямую (1)  ограничения  дойдём до точки пересечения
(2) и (3) ограничений (точка F).

[pic 9]

 Найдём координаты этой точки решив систему уравнений.

3x1+x2[pic 10]

x1+2x2 =7

Получим x1=0,6 и x2=3,2.

Подставим координаты точки F в ограничение (1) и узнаем на сколько можно увеличить ресурс.

-1*0,6 + 4*3,2 = 12,2

z(F)= -1*0,6 + 1*3,2 = 2,6

Аналогично определим на сколько можно увеличить ресурс соответствующий (2) ограничению.

Перемещая прямую 2  ограничения  мы дойдём до точки пересечения
(1) и (3) ограничений (точка C).

Найдём координаты этой точки решив систему уравнений.

-x1+4x2 9[pic 11]

x1+2x2=7