Условия разрешимости задачи и единственности решения

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

Если же область неограничена, то дело обстоит по-иному. В этом случае одна из задач (на максимум или на минимум целевой функции) или обе эти задачи могут оказаться неразрешимыми.

Полученные результаты можно сформулировать следующим образом.

Область допустимых планов задачи либо пуста, либо непуста. Если она пуста, то задача неразрешима, поскольку она не имеет даже допустимых планов.

Если область непуста, то она либо ограничена, либо неограниченна. Если область ограничена, то задача имеет решение.

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

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

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

Такие методы существуют. Наиболее известным среди них является так называемый симплекс-метод. Этот метод позволяет решить любую задачу линейного программирования (либо доказать ее неразрешимость). Он лежит в основе разнообразных алгоритмов расчета оптимального плана. Известны многочисленные компьютерные реализации таких алгоритмов. Один из удобных вариантов встроен в Excel. Для проведения соответствующих расчетов следует обратиться в Excel к программе «Поиск решения».

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

Построение области допустимых планов

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

Множество решений этого уравнения соответствует прямой на координатной плоскости. Чтобы изобразить прямую достаточно найти две ее точки. Найдем точки на осях координат. Для этого положим в уравнении x₂ = 0. Получим x₁ = 1650. Изобразим соответствующую точку на оси 0x₁ (точка А₁ на рис 1.2.). Теперь положим в уравнении x₁ = 0. Получим x₂ = 2750. Изобразим соответствующую точку А₂ на оси 0x₂.

Соединим точки А₁ и А₂ прямой линией. Мы получили граничную прямую искомой полуплоскости.

Эта прямая делит координатную плоскость на две полуплоскости. Для определения полуплоскости, соответствующей множеству решений неравенства, выберем точку, не лежащую на граничной прямой (например, начало координат), и подставим ее координаты в наше неравенство. Получим 0 £ 825. Неравенство верное. Следовательно, искомой полуплоскостью является та, которая содержит начало координат, и тем самым лежит слева от граничной прямой.

Рис. 1.2. Граничная прямая по ресурсу Мука

Если бы мы вместо начала координат взяли, например, точку с координатами (2000, 0), лежащую правее и выше нашей прямой, и подставили бы ее координаты в левую часть неравенства, то получили бы 1000 £ 825. Неравенство неверно, следовательно, выбранная точка не принадлежит искомой полуплоскости. Искомой оказывается все та же левая полуплоскость.

Теперь найдем полуплоскость, соответствующую второму неравенству системы ограничений. Ее граничная прямая проходит через точку В₁ с координатами (1600; 0), лежащую на оси 0x₁, и через точку с координатами (0; 8000) на оси 0x₂. Для удобства изображения заменим вторую точку другой точкой, лежащей на той же прямой.

Для этого положим x₂ = 3000. Тогда из уравнения прямой получаем x₁ = (480 – 0, 06*3000) / 0, 3 = 1000. В качестве B₂ возьмем точку с координатами (1000, 3000). Соединим прямой линией точки В₁ и B₂ (рис. 1.3).

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

Аналогично строятся границы по остальным ресурсам (рис. 1.4). Границе по Яйцу соответствует прямая C1C2, границе по Сахару прямая D₁D₂, границе по Труду прямая E₁E₂, по Оборудованию 1 прямая F₁F₂, по Оборудованию 2 прямая G1G2. Каждый раз следует выбрать ту полуплоскость, которая содержит начало координат.

Условия ограниченности недельного спроса (x₁, x₂ ограничены величиной 3000) определяют горизонтальную и вертикальную границы чертежа. Неотрицательность переменных x₁ и x₂ соответствует первой координатной четверти. Таким образом, четыре стороны квадрата соответствуют ограничениям модели.

Рис. 1.3. Граничные прямые по ресурсам Мука и Масло

Рис. 1.4. Граничные прямые по всем ресурсам

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

Любая точка данного шестиугольника удовлетворяет всем ограничениям задачи и соответствует допустимому плану. Если при этом точка лежит на стороне шестиугольника, то ее координаты, подставленные в левую часть ограничения-неравенства, обращают ограничение в равенство. Такое ограничение называется связанным. Данная ситуация означает, что реализация плана требует полного использования соответствующего ресурса.

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

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

Точки, удовлетворяющие всем ограничениям – это точки нашего шестиугольника. Его границы соответствуют сырьевым ресурсам.

Линии Труда и Оборудования 1 и 2 (прямые E₁E₂, F₁F₂, G₁G₂) оказываются в стороне. Это означает, что при реализации любого допустимого плана данной задачи трудовые ресурсы и производственные мощности не будут, по существу, ограничивать наши возможности, так как они в более жесткой форме ограничены запасами сырья. Следовательно, если у нас появится возможность изменить доступные объемы ресурсов, то ее следует направить в первую очередь на изменение запасов сырья.

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

Во-первых, область допустимых планов непустая и ограничена. Следовательно, оптимальный план существует.

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

Построение градиента и определение оптимального плана

Обратимся к целевой функции. Ее градиент есть вектор (32; 27). Для решения задачи следует изобразить этот вектор в виде стрелки с началом в точке (0; 0) и концом в точке (32; 27).

Такая стрелка является короткой и поэтому плохо различимой на чертеже. Однако длина этой стрелки не играет никакой роли при решении задачи. Важно лишь ее направление. Если обе координаты точки (32; 27) умножить или разделить на одно и то же положительное число, то изменится лишь длина стрелки, но не ее направление. Поэтому на результате решения задачи это не скажется.

Рис. 1.5. Построение оптимального плана

Удлиним стрелку до границы нашего рисунка. Все линии уровня целевой функции параллельны друг другу и перпендикулярны градиенту. На рис. 1.4 пунктиром изображены линии, соответствующие различным значениям целевой функции, начиная от 10000 и с шагом 16000. Разумеется, такие линии могут быть построены для любых значений целевой функции, они параллельны и все вместе покрывают координатную плоскость. Градиент показывает направление роста целевой функции. Мы решаем задачу на максимум. Чем больше значение целевой функции, тем лучше. Однако при слишком больших значениях пунктирная линия уровня окажется за пределами области допустимых планов.

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

Найдем координаты оптимального плана. Приближенно их можно определить по чертежу. Для точного расчета необходимо решить соответствующую систему уравнений. Точка L лежит на границе первого и четвертого ограничений. Составляем систему уравнений:

Решив эту систему, получаем компоненты оптимального плана: x₁ = 1250 и x₂ = 667. Таким образом, оптимальный план X*_max равен: .

Он предписывает выпустить 1250 кг Печенья и 667 (точнее, 666, 667) кг Бисквитов.

Для определения оптимума следует подставить компоненты оптимального плана в целевую функцию задачи. Оптимум Z*_max определяется равенством:

.

Таким образом, реализация выпущенной продукции даст выручку в размере 58000 руб. Задача решена. Теперь следует обратиться к экономическому содержанию задачи и проанализировать полученный результат.

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