Согласно проведенным исследованиям графический метод решения задач линейного программирования основан на геометрической интерпретации данной задачи. Этот метод наиболее прост и нагляден, в отличии от симплекс метода с помощью графического метода мы можем найти одновременно решение как максимума, так и минимума. В современной экономике графический метод решения ЗЛП очень популярен из-за его наглядности. В современных компаниях это метод используется чаще всего для выявления максимального дохода предприятия, а также максимального объема производства. В следующей задаче наглядно продемонстрирован пример использования графического метода в современной экономике.
Компьютерная компания занимается изготовлением мониторов и мышек, но их ресурсы производства ограничены (обшивка, USB провод, материнская плата) (табл. 1).
Необходимо составить план выпуска продукции с учетом имеющихся ресурсов, обеспечивающих наивысшую прибыль.
Выше приведены условия, которые являются экономической постановкой задачи. Теперь же необходимо составить математическую модель задачи.
Таблица 1
Нормы затраты на одну ед. продукции, количество ресурсов, и прибыль от реализации одной единицы продукции
|
Виды ресурсов |
Виды продукции |
Количество ресурсов |
|
|
Монитор |
Мышь |
||
|
Обшивка |
3 |
2 |
27 |
|
USB провод |
2 |
4 |
28 |
|
Материнская плата |
2 |
3 |
23 |
|
Прибыль |
4 |
7 |
|
Пусть x и y – количество выпускаемых мониторов и мышек. Тогда следует, что общая прибыль от продажи всей продукции составит Z = 4X + 7Y → max. При этом общий расход обшивки равен 3x + 2y и он не должен быть больше имеющегося запаса 27. Таким образом они ограничиваются 3x + 2y ≤ 27. Так же учитываются ограничения по USB проводу и материнской плате: 2x + 4y ≤ 28, 2x + 3y ≤ 23. Следовательно, если объем больше нуля, то x ≥ 0, y ≥ 0. Тогда математическая модель задачи имеет вид:
Z = 4X + 7Y → max
3x + 2y ≤ 27
2x + 4y ≤ 28
2x + 3y ≤ 23
x ≥ 0, y ≥ 0.
Таким образом, цель данной задачи состоит в том, чтобы найти положительные значения x ≥ 0, y ≥ 0, где Z принимает наивысшее значения.
Для начала составим ОДР, затем найдем Zmax. Начнем решение задачи с геометрического представления ОДР. Уравнение x ≥ 0, y ≥ 0 ограничивают ОДР 1 четвертью. Система уравнений составляет на координатной плоскости xOy некоторую полуплоскость. Найдем полуплоскости на которых выполняются эти уравнения. Для этого нужно просто взять некую произвольную точку, через которую не проходит граничная прямая и проверить, удовлетворяет ли данная точка уравнению. Если данная точка подходит,то это уравнение выполняется на полуплоскости, на которой находится произвольная точка. В обратном случае берется полуплоскость, на которой не находится произвольная точка. Берем в качестве произвольной точки начало координат О (0;0). Обратим внимание, что при построении ОДР систему уравнений удобнее выражать в отрезках.
Для данной задачи области допустимых решений – это множество точек многоугольника OIUYT. На рисунке 1 показаны уравнения прямых, а стрелками указаны области, где они выполняются.
Составим геометрическую интерпретацию уравнения Z = 4X + 7Y →max.
Уравнение Z = C1X + C2Y = 4X + 7Y , при значении Z = Z1, то Z1 = 4X + 7Y. Если изменить значение Z, то получим семейство параллельных прямых, называемых линями уровня. C̄ = (С1; С2) перпендикулярен каждой из линий уровня.
Вектор C показывает направление наивысшего возрастания уравнения. Перпендикулярно к вектору С нужно провести линию уровня Z = 0. Параллельно перенесем прямую Z = 0 и найдем крайнюю точку, где Z = 4X + 7Y достигает максимума (pис. 2).
Рис. 2.
Из-за то, что точка U находится на пересечении прямых 2 и 3, координаты U определяются системой
2x + 4y = 28
2x + 3y = 23
где U (4, 5), Zmax = Z (U)= 4×4 + 7×5 = 51. Этот способ решения задачи называется графическим.
Ответ: необходимо выпускать 4 монитора и 5 мышек, тогда прибыль составит 51 денежных единиц.
Выполнив данную задачу мы можем прийти к выводу, что графический метод прост в использовании, но он не подходит для вычисления больших величин. Графический метод применяется для решения задач, которые имеют две переменные, в отдельных случаях три переменные, но тогда решением задачи будет являться полупространство, находящаяся по одну сторону плоскости. Роль областей будут играть многогранники, являющиеся пересечением полупространств.