Мы рассмотрели сейчас предельно упрощенные примеры, преследуя исключительно иллюстративные цели, однако их анализ позволит осмыслить общие идеи и математические методы, лежащие в основе решения подобных задач. В обоих примерах множество допустимых планов определяется точками выпуклого многогранника, полученного в результате пересечения полупространств, заданных линейными неравенствами (2.2.1) и (2.2.2). Линейная целевая функция при двух переменных задает на плоскости семейство параллельных прямых, при трех переменных – семейство параллельных плоскостей в трехмерном пространстве, а в случае n переменных – семейство параллельных ( n- 1)–мерных пространств (гиперплоскостей) в n -мерном пространстве. Линейные ограничения и линейная целевая функция появились в наших примерах благодаря предположению о пропорциональной зависимости переменных и постоянных факторов. В силу этого подобный класс задач называют задачами линейного программирования. Геометрически решение задачи линейного программирования сводится к следующим этапам: а) определение области допустимых планов, т.е. построение соответствующего ограничениям многогранника; б) перемещение гиперплоскости целевой функции в пространстве параллельно самой себе до тех пор, пока она не будет максимально (минимально) удалена от начала координат и при этом будет иметь хотя бы одну общую точку с многогранником допустимых планов. Этой точкой, как мы видели, будет вершина многогранника, хотя может быть грань или ребро в случае параллельности гиперплоскости целевой функции какой-либо грани или ребру многогранника. Координаты этой вершины и будут определять оптимальное решение. Если целевая гиперплоскость касается грани или ребра, то в этом случае получается множество оптимальных планов, имеющих одно и тоже максимальное (либо минимальное) значение целевой функции. Из анализа решения примеров делаем важный вывод: оптимальному плану соответствует точка в области допустимых планов (возможно неединственная), являющаяся вершиной многогранника допустимых планов. На этом основана идея метода решения задачи линейного программирования, заключающаяся в том, что для нахождения оптимального плана достаточно просматривать лишь вершины многогранника допустимых планов.
100 Решение (план), которому соответствует вершина многогранника, называется базисным. Для нахождения базисного плана необходимо решить систему из n линейных уравнений с n неизвестными. Разработанный в 1949г. Дж. Данцигом симплекс-метод основан на последовательном переходе от одной вершины многогранника допустимых планов к соседней, в которой линейная целевая функция принимает лучшее (не худшее) значение до тех пор, пока не будет найдено оптимальное решение. Рассмотренные выше примеры позволяют сформулировать общую задачу линейного программирования. Дана система m линейных неравенств с n переменными
a 11 х 1 + a 12 х 2 + …+ a1n хn ≤ b 1
a 21 х 1 + a 22 х 2 + …+ a2n хn ≤ b 2 ……………………………….. (2.2.3)
am 1 х 1 + a m2 х 2 + …+ amn хn ≤ b m
и линейная функция
F = c 1 х 1 + c 2 х 2 + … + cnхn . (2.2.4) Необходимо найти такое решение системы Х = ( х 1, х 2,… , хn ), где
х j ≥ 0 ( j =1,2,…n), (2.2.5) при котором линейная функция F (2.2.4) принимает оптимальное (максимальное или минимальное) значение. Система (2.2.3) называется системой ограничений, а функция F – целевой функцией, критерием или функцией цели. Более кратко общую задачу линейного программирования можно представить в виде:
F =∑ = n j jjxc 1 甸 max( min) при ограничениях: ∑ = n j jijxa 1 ≤ bi ( i =1,2,…, m ),
xj ≥ 0 ( j =1,2,… n ). Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение системы ограничений (2.2.3), удовлетворяющее условию (2.2.5), при котором линейная функция (2.2.4) принимает оптимальное (максимальное или минимальное) значение. В рассматриваемой задаче все неравенства вида “ ≤ “, хотя могут быть и вида “≥“, каждое такое неравенство, как мы видели на примерах, определяет полупространство в n -мерном пространстве.
101 Постоянные коэффициенты aij являются, как правило, нормами расхода i-го ресурса на производство единицы j- го изделия (продукта). Коэффициенты bi задают предельные объемы использования i -го ресурса. Коэффициенты cj определяют удельную прибыль (или затраты) от производства единицы j -го изделия (продукта). Если мы какую-либо производственную задачу смоделировали в виде задачи линейного программирования, то в ходе ее решения можно получить следующие результаты: 1.Ограничения могут оказаться несовместными, и задача не имеет решения. 2. Целевая функция не ограничена в области допустимых планов, ее максимум ( или минимум) → + ∞ ( - ∞). 3. Оптимальное решение единственное (целевая функция касается области допустимых планов в единственной вершине, ее координаты и определяют оптимальный план). 4. Существует некоторое множество оптимальных решений (планов). Если задача экономически поставлена правильно, то 1-й и 2-ой случаи исключаются.
Ви переглядаєте статтю (реферат): «Общая задача линейного программирования» з дисципліни «Математична економіка»
