.ПРИМЕР ГРАФИЧЕСКОГО РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Построение области допустимых планов
Приведем графическое решение задачи об изготовлении Печенья и Бисквитов. Сначала изобразим границу полуплоскости, соответствующую множеству решений первого неравенства. Для этого неравенство заменим равенством:
.
Множество решений этого уравнения соответствует прямой на координатной плоскости. Чтобы изобразить прямую достаточно найти две ее точки. Найдем точки на осях координат. Для этого положим в уравнении x2 = 0. Получим x1 = 1650. Изобразим соответствующую точку на оси 0x1 (точка А1 на Рис. 2.2 ). Теперь положим в уравнении x1 = 0. Получим x2 = 2750. Изобразим соответствующую точку А2 на оси 0x2.
Соединим точки А1 и А2 прямой линией. Мы получили граничную прямую искомой полуплоскости.
Эта прямая делит координатную плоскость на две полуплоскости. Для определения полуплоскости, соответствующей множеству решений неравенства, выберем точку, не лежащую на граничной прямой (например, начало координат), и подставим ее координаты в наше неравенство. Получим 0 £ 825. Неравенство верное. Следовательно, искомой полуплоскостью является та, которая содержит начало координат, и тем самым лежит слева от граничной прямой.
Рис. 2.2.
Граничная прямая по ресурсу Мука
Если бы мы вместо начала координат взяли, например, точку с координатами (2000, 0), лежащую правее и выше нашей прямой, и подставили бы ее координаты в левую часть неравенства, то получили бы 1000 £ 825. Неравенство неверно, следовательно, выбранная точка не принадлежит искомой полуплоскости. Искомой оказывается все та же левая полуплоскость.
Теперь найдем полуплоскость, соответствующую второму неравенству системы ограничений. Ее граничная прямая проходит через точку В1 с координатами (1600; 0), лежащую на оси 0x1, и через точку с координатами (0; 8000) на оси 0x2. Для удобства изображения заменим вторую точку другой точкой, лежащей на той же прямой.
Для этого положим x2 = 3000. Тогда из уравнения прямой получаем x1 = (480 – 0,06*3000) / 0,3 = 1000. В качестве B2 возьмем точку с координатами (1000, 3000). Соединим прямой линией точки В1 и B2 (Рис. 2.3 ).
Рис. 2.3.
Граничные прямые по ресурсам Мука
и Масло
Из двух возможных полуплоскостей опять следует выбрать ту, которая содержит начало координат.
Аналогично строятся границы по остальным ресурсам (Рис. 2.4 ). Границе по Яйцу соответствует прямая C1C2, границе по Сахару прямая D1D2, границе по Труду прямая E1E2, по Оборудованию 1 прямая F1F2, по Оборудованию 2 прямая G1G2. Каждый раз следует выбрать ту полуплоскость, которая содержит начало координат.
Условия ограниченности недельного спроса (x1, x2 ограничены величиной 3000) определяют горизонтальную и вертикальную границы чертежа. Неотрицательность переменных x1 и x2 соответствует первой координатной четверти. Таким образом, четыре стороны квадрата соответствуют ограничениям модели.
Пересечение всех полученных полуплоскостей определяет шестиугольник, примыкающий к началу координат. Это и есть область допустимых планов.
Любая точка данного шестиугольника удовлетворяет всем ограничениям задачи и соответствует допустимому плану. Если при этом точка лежит на стороне шестиугольника, то ее координаты, подставленные в левую часть ограничения-неравенства, обращают ограничение в равенство. Такое ограничение называется связанным. Данная ситуация означает, что реализация плана требует полного использования соответствующего ресурса.
Точка, лежащая в вершине шестиугольника, обращает в равенство сразу два ограничения и соответствует полному использованию сразу двух ресурсов. Точек, лежащих на пересечении сразу трех или большего числа ограничений, в нашей задаче не существует.
Точка, лежащая вне шестиугольника, не удовлетворяет хотя бы одному ограничению. Графики позволяют не просто констатировать недопустимость такой внешней точки, но и определить, каким именно ограничениям она не удовлетворяет, каких именно ресурсов не хватает для реализации плана. Вся внешняя область разбивается на многоугольники, точки которых не удовлетворяют тем или иным ограничениям.
 |
Рис. 2.4. Граничные прямые по всем ресурсам
Точки, удовлетворяющие всем ограничениям – это точки нашего шестиугольника. Его границы соответствуют сырьевым ресурсам.
Линии Труда и Оборудования 1 и 2 (прямые E1E2, F1F2, G1G2) оказываются в стороне. Это означает, что при реализации любого допустимого плана данной задачи трудовые ресурсы и производственные мощности не будут, по существу, ограничивать наши возможности, так как они в более жесткой форме ограничены запасами сырья. Следовательно, если у нас появится возможность изменить доступные объемы ресурсов, то ее следует направить в первую очередь на изменение запасов сырья.
Построение области допустимых планов использует лишь систему ограничений. Для определения оптимального плана необходимо привлечь целевую функцию. Однако кое-что про оптимальный план можно сказать уже сейчас.
Во-первых, область допустимых планов непуста и ограничена. Следовательно, оптимальный план существует.
Во-вторых, оптимальный планом наверняка окажется одна из вершин шестиугольника. Если оптимальный план у нашей задачи единствен, то этим планом будет одна вершина. Если же он не единствен, то этим оптимальным планом окажутся две соседние вершины, а вместе с ними и все точки стороны шестиугольника.
