Графический метод решения задачи оптимального планирования: подробный разбор

Введение в задачу и метод

Представьте себе типичную ситуацию: у производственной фирмы есть несколько видов продукции, которые она может выпускать. Для их изготовления требуются ресурсы — сырье, рабочее время оборудования, человеческий труд. Проблема в том, что все эти ресурсы ограничены. Каждый день руководство стоит перед выбором: сколько единиц продукта «А» и сколько единиц продукта «Б» произвести, чтобы, уложившись в лимиты, получить максимальную прибыль?

Именно для таких задач и было разработано линейное программирование. А когда речь идет о двух видах продукции, на помощь приходит один из самых наглядных инструментов — графический метод. Его прелесть в том, что он позволяет буквально увидеть задачу на плоскости: увидеть все возможные производственные планы и найти среди них тот самый, единственный, который принесет наибольший доход. Этот метод является фундаментом для понимания более сложных подходов и идеально подходит для решения контрольных работ.

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

Шаг 1. Как перевести бизнес-задачу в точную математическую модель

Формализация — это ключ к решению. Нам нужно превратить таблицу с данными о ресурсах и ценах в строгую систему уравнений и неравенств. Давайте сделаем это последовательно.

1. Вводим переменные.
Пусть x1 — это количество единиц продукта А, которое мы планируем произвести, а x2 — количество единиц продукта В. Это наши неизвестные, которые нам предстоит найти.

2. Формулируем целевую функцию.
Наша цель — максимизировать прибыль от продаж. Цена одной единицы продукта А составляет 201 руб., а продукта В — 187 руб. Общая прибыль (обозначим ее Z) будет суммой прибылей от продажи обоих продуктов. Так мы получаем главное уравнение нашей модели — целевую функцию:
Z = 201×1 + 187×2 → max

3. Составляем систему ограничений.
Теперь учтем наши ограниченные ресурсы. Для каждого из них мы составим отдельное неравенство:

• Сырье: На одну единицу продукта А уходит 3 кг сырья, а на продукт В — 1 кг. Общий запас сырья — 216 кг. Значит, суммарный расход не должен превышать этот лимит: 3×1 + 1×2 ≤ 216.
• Оборудование: Производство продукта А требует 1 час работы оборудования, а продукта В — 3 часа. Всего у нас есть 144 станко-часа: 1×1 + 3×2 ≤ 144.
• Трудоресурсы: На продукт А тратится 7 человеко-часов, на продукт В — 1. Общий фонд рабочего времени — 780 часов: 7×1 + 1×2 ≤ 780.

4. Добавляем условие неотрицательности.
Очевидно, что мы не можем произвести отрицательное количество продукции. Поэтому добавляем еще два условия: x1 ≥ 0 и x2 ≥ 0. Это условие ограничивает наш поиск решения первым квадрантом координатной плоскости.

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

Шаг 2. Построение области допустимых решений, которая покажет все возможные планы

Этот шаг — сердце графического метода. Мы превратим систему неравенств в конкретную геометрическую фигуру на плоскости. Любая точка внутри этой фигуры будет соответствовать реальному производственному плану, который не нарушает ограничений по ресурсам. Этот многоугольник называется областью допустимых решений (ОДР).

Построение выполняется в несколько этапов:

1. Превращаем неравенства в уравнения. Для каждого ограничения мы строим соответствующую ему прямую.
   • 3x1 + x2 = 216 (Ограничение по сырью)
   • x1 + 3x2 = 144 (Ограничение по оборудованию)
   • 7x1 + x2 = 780 (Ограничение по трудоресурсам)
2. Находим координаты для построения прямых. Для каждой прямой найдем по две точки, обычно это точки пересечения с осями координат.
   • Для 3x1 + x2 = 216: если x1=0, то x2=216; если x2=0, то x1=72. Точки: (0; 216) и (72; 0).
   • Для x1 + 3x2 = 144: если x1=0, то x2=48; если x2=0, то x1=144. Точки: (0; 48) и (144; 0).
   • Для 7x1 + x2 = 780: если x1=0, то x2=780; если x2=0, то x1≈111,4. Точки: (0; 780) и (111,4; 0).
3. Чертим прямые на графике. На осях x1 и x2 откладываем найденные точки и соединяем их, получая три прямые.
4. Определяем нужные полуплоскости. Каждая прямая делит плоскость на две части. Нам нужно определить, какая из них соответствует нашему неравенству (со знаком ≤). Самый простой способ — подставить в неравенство координаты точки (0;0). Например, для сырья: 3(0) + 0 ≤ 216. Это верно, значит, нам нужна полуплоскость, содержащая начало координат. Проделываем это для всех ограничений.
5. Находим общую область. Искомая ОДР — это многоугольник, образованный пересечением всех разрешенных полуплоскостей в первом координатном квадранте (так как x1 ≥ 0, x2 ≥ 0).

Мы определили все возможные варианты производственной программы. Теперь среди этих бесконечных вариантов нам нужно найти один-единственный, который принесет максимальную прибыль.

Шаг 3. Поиск оптимальной точки для получения максимальной прибыли

Теперь в игру вступает наша целевая функция Z = 201×1 + 187×2. Наша задача — найти такую точку (x1, x2) внутри или на границе области допустимых решений, в которой Z принимает максимальное значение.

Для этого мы используем вектор-градиент и линию уровня.

1. Строим вектор-градиент. Это вектор N = (201; 187), составленный из коэффициентов целевой функции. Он указывает направление, в котором функция Z растет быстрее всего.
2. Строим линию уровня. Это сама прямая 201x1 + 187x2 = const. Чтобы построить ее, зададим Z произвольное значение (например, 0, чтобы линия прошла через начало координат) и проведем прямую, перпендикулярную вектору-градиенту.
3. Ищем оптимум. Теперь мысленно двигаем линию уровня параллельно самой себе в направлении вектора-градиента. Мы перемещаем ее до тех пор, пока она не коснется самой дальней точки нашей области допустимых решений. Эта точка и будет оптимальным решением, так как в ней целевая функция достигнет своего максимума.

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

Визуально определив, в какой вершине находится оптимум, мы находим ее точные координаты. Эта точка лежит на пересечении двух прямых-ограничений. Чтобы найти ее координаты, нужно решить систему уравнений этих прямых. В нашем случае, судя по наклону, это будут прямые, соответствующие ограничениям по сырью и оборудованию:

{ 3x1 + x2 = 216
{ x1 + 3x2 = 144

Решив эту систему, мы найдем искомые значения x1 и x2, которые и представляют собой оптимальный план производства.

Мы нашли оптимальный план производства. Но что, если мы посмотрим на задачу с другой стороны — со стороны ценности наших ограниченных ресурсов? Для этого существует двойственная задача.

Шаг 4. Формулировка двойственной задачи, или сколько на самом деле стоят наши ресурсы

У каждой задачи линейного программирования есть «зеркальное отражение» — двойственная задача. Если исходная (прямая) задача отвечает на вопрос «что и в каком количестве производить?«, то двойственная отвечает на вопрос «какова объективная ценность каждого из наших ограниченных ресурсов?«.

Давайте сформулируем ее по формальным правилам. Введем три новые переменные — y1, y2, y3. Это и есть двойственные оценки, которые будут соответствовать ценности каждого из наших ресурсов: сырья, оборудования и трудоресурсов.

• Целевая функция. В прямой задаче мы максимизировали прибыль. В двойственной мы будем минимизировать суммарную ценность всех имеющихся ресурсов. Коэффициентами при переменных y будут объемы ресурсов из прямой задачи:
  
  F = 216y1 + 144y2 + 780y3 → min
• Ограничения. Ограничения для двойственной задачи формируются из столбцов матрицы прямой задачи.
  • Первое ограничение относится к продукту А: 3y1 + 1y2 + 7y3 ≥ 201
  • Второе ограничение — к продукту В: 1y1 + 3y2 + 1y3 ≥ 187
• Условие неотрицательности: y1, y2, y3 ≥ 0.

Экономический смысл этих ограничений очень глубок: суммарная ценность ресурсов, затраченных на производство одной единицы любого продукта, не может быть ниже цены этого продукта. Иными словами, производство не должно быть убыточным с точки зрения «внутренней» стоимости ресурсов.

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

Шаг 5. Анализ эффективности ресурсов через условия дополняющей нежесткости

Решения прямой и двойственной задач связаны фундаментальной теоремой о дополняющей нежесткости. Она дает нам мощный инструмент для экономического анализа, позволяя определить, какие ресурсы являются «узкими местами» (дефицитными), а какие находятся в избытке.

Суть теоремы можно выразить двумя простыми правилами:

1. Если в оптимальном плане ресурс не израсходован полностью (соответствующее ограничение в прямой задаче выполняется как строгое неравенство), то его двойственная оценка (ценность) равна нулю. Это логично: зачем ценить то, чего у нас и так в избытке?
2. Если двойственная оценка ресурса больше нуля, то этот ресурс полностью израсходован (соответствующее ограничение в прямой задаче выполняется как точное равенство). Это и есть наше «узкое место» или дефицитный ресурс.

Используя эти условия, мы можем найти значения y1, y2, y3. Предположим, мы нашли оптимальное решение прямой задачи (x1*, x2*). Мы подставляем его в наши исходные ограничения:

• Если 3x1* + x2* < 216, то y1 = 0.
• Если x1* + 3x2* < 144, то y2 = 0.
• Если 7x1* + x2* < 780, то y3 = 0.

Поскольку оптимальная точка лежала на пересечении первых двух ограничений (сырье и оборудование), то именно эти ресурсы были израсходованы полностью. А вот третье ограничение (трудоресурсы), скорее всего, будет иметь «запас». Это значит, что y3 = 0. Полученные ненулевые значения y1 и y2 покажут, на сколько увеличится общая прибыль Z, если мы увеличим запас дефицитного ресурса (сырья или оборудования) на одну единицу. Это и есть их предельная эффективность.

Мы получили решения для обеих задач и нашли ценность ресурсов. Чтобы быть полностью уверенными в результате перед сдачей контрольной, осталось выполнить финальную проверку.

Шаг 6. Финальная проверка для полной уверенности в результате

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

Шаг 1: Проверка допустимости решения прямой задачи.
Подставьте найденные оптимальные значения x1* и x2* в исходную систему ограничений. Убедитесь, что ни одно из неравенств не нарушается.

• 3x1* + x2* ≤ 216
• x1* + 3x2* ≤ 144
• 7x1* + x2* ≤ 780

Если все условия выполняются, ваш план производства является допустимым.

Шаг 2: Проверка по основной теореме двойственности.
Это ключевой этап проверки. Основная теорема двойственности гласит, что в оптимальных точках значения целевых функций прямой и двойственной задач должны совпадать:

Z_max = F_min

Вычислите значение Z_max, подставив x1* и x2* в целевую функцию Z = 201×1 + 187×2.
Затем вычислите значение F_min, подставив найденные y1*, y2*, y3* в целевую функцию F = 216y1 + 144y2 + 780y3.
Если полученные значения совпали, вы можете быть практически на 100% уверены в правильности всего решения.

Теперь, когда мы не только решили задачу, но и всесторонне ее проанализировали и проверили, подведем итоги нашего пути.

Заключение и выводы

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

Мы не просто нашли абстрактные числа. Мы определили оптимальную производственную программу, которая гарантирует предприятию максимальную прибыль при имеющихся ограничениях. Что еще более важно, с помощью двойственных оценок мы заглянули «внутрь» производственного процесса. Мы выявили дефицитные ресурсы, так называемые «узкие места», которые сдерживают рост производства. Теперь руководство знает, что увеличение запасов именно этих ресурсов принесет наибольшую отдачу.

Освоенный вами алгоритм — от построения модели до анализа двойственности — это универсальный и мощный инструмент. Он применим к широкому классу задач по оптимизации не только в производстве, но и в логистике, финансах и планировании. Вы научились не просто решать задачу, а извлекать из ее решения ценные управленческие выводы.