1.5. Графическое решение линейной производственной задачи с двумя переменными

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

Воспользуемся тем, что в оптимальной производственной программе х2* = 0, х4* = 0, т.е. продукция второго и четвертого вида не производится. Предположим, что второй и четвертый виды продукции мы не намеревались выпускать с самого начала.

Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию.

Исходные данные примут вид:

Вектор удельной прибыли

Математическая модель задачи будет выглядеть следующим образом:

Найти производственную программу Х (х1, х3),

максимизирующую прибыль Z = 38x₁ + 28x₃ → max,

при условии ограниченности

имеющихся ресурсов 3х1 + 3х3 ≤ 186

2х1 + х3 ≤ 102

4х1 + 2х3 ≤ 196

где по смыслу задачи х1 ≥ 0, х3 ≥ 0

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

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

Каждое линейное неравенство системы, выражающей условие ограниченности имеющихся ресурсов, на графике определяет полуплоскость допустимых значений переменных этого неравенства вместе с ограничивающей данную полуплоскость прямой, множество точек которой является решением соответствующего неравенству линейного уравнения:

3х1 + 3х3 = 186 - ограничивающая прямая I

2х1 + х3 = 102 - ограничивающая прямая II

4х1 + 2х3 = 196 - ограничивающая прямая III

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

Построим вектор-градиент grad Z = (0, 0); (38, 28), указывающий направление наискорейшего возрастания функции Z.

Линии уровня функции Z перпендикулярны вектору-градиенту grad Z и образуют семейство параллельных прямых.

Перемещаем линию уровня функции Z в направлении вектора-градиента grad Z, не выходя при этом за пределы допустимого множества (четырехугольника OQRS), до крайней точки допустимого множества.

Определяем, что максимального значения в области допустимого множества функция Z достигнет в точке R, которая является пересечением I и III прямых. Следовательно, координаты этой точки определяют оптимальный план производства, и мы можем их найти, решив систему уравнений:

3х1 + 3х3 = 186

4х1 + 2х3 = 196

1). Выразим переменную х3 через второе уравнение системы:

х3 = 196 – 4х1 = 98 – 2х1

2

2). Подставим полученное выражение 3). Найдем 4). Найдем максимальную

в 1-е уравнение и найдем значение х1: значение х3: прибыль:

3х1 + 3 (98 – 2х1) = 186 108 + 3х3 = 186

3х1 + 294 – 6х1 = 186 3х3 = 78 Z = 38х1 + 28х3

- 3х1 = - 108

х1* = 36 х3* = 26 Z(max) = 38*36 + 28*26 = 2096