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

Задана задача линейного  программирования со следующим условием:

2х₁+4х₂<=16;

-4х₁+2х₂<=8;

1х₁+3х₂>=9;

F=х₁+х₂;

х₁>= 0, х₂>= 0.

1.1 Найти графическое  решение задачи линейного программирования  (найти max и min целевой функции).

 1.2 Найти решение задачи линейного программирования средствами Excel  «Поиск решения» (найти max и min целевой функции). Привести скриншоты таблицы ограничений с отображением формул, диалогового окна «Поиск решения» с введенными в него ограничениями, а также таблицы нахождения max и min целевой функции.

 

1.1 Преобразуем систему неравенств в систему уравнений и запишем ниже:

2х₁+4х₂=16;

-4х₁+2х₂=8;

1х₁+3х₂=9.

А также найдем производную F по х₁ и х₂

F’ (1;1).

Выразим из каждого выражения  х₂.

х₂=4-0,5х₁;

х₂=4+2х₁;

х₂=3-0,3х₁.

Найдем точки пересечения с осями х₁ и х₂ и проведем через них прямые.

1. (0;4) (8;0)
2. (0;4) (-2;0)
3. (0;3) (9;0).

 

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

  Как видно из графика точка max образуется при пересечении прямых (1) и (3). Чтобы найти ее координаты и значение целевой функции, следует совместно решить уравнения 1 и 3:

2х₁+4х₂=16;

1х₁+3х₂=9.

В результате получим х₁=6 и х₂=1. Это и есть оптимальное решение. При этом значение целевой функции будет равным Fmax=1*6+1*1=7.

Теперь найдем координаты точки min и значение целевой функции. Как видно из графика точка min образуется при пересечении прямой (3) и оси ординат. Чтобы найти ее координаты и значение целевой функции, следует совместно решить уравнения:

1х₁+3х₂=9;

х₁=0.

В результате получим х₁=0 и х₂=3. Это и есть оптимальное решение. При этом значение целевой функции будет равным Fmin=1*0+1*3=3.

Ответ: max (6;1) Fmax=7; min (0;3) Fmin =3.

 

1.2 Заполним в Excel таблицу с  заданными ограничениями.

 

   

 

 

 

 

 

 

Рисунок 1- Таблица ограничений с отображением формул.

 

Для оптимизации в Excel используется инструмент Поиск решения, куда вносятся искомые ограничения (рисунок 2).

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2- Диалоговое окно «Поиск решения» для нахождения max.

После ввода всех ограничений  и других условий следует нажать кнопку «Выполнить» для решения поставленной задачи. Исходная таблица ограничений примет следующий вид.

 

 

 

 

 

 

 

 

 

 

 

Рисунок 3- Нахождение max целевой функции.

 

Аналогично находим min целевой функции.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 4- Диалоговое окно «Поиск решения» для нахождения min.

 

Исходная таблица ограничений  примет следующий вид.

 

 

 

 

 

 

 

 

 

 

 

Рисунок 5- Нахождение min целевой функции.