Графический способ решения ЗЛП.

Введение.

Многие задачи, с которыми приходится иметь дело в повседнев­ной практике, являются многовариантными. Среди множе­ства возможных вариантов в условиях рыночных отно­шений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, эко­номические и технологические возможности. В связи с этим возникла необхо­димость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику? Такие методы объединяются под общим названием — математическое программирование.

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

Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием опти­мальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет матема­тическую модель. Математическая модель задачи — это отражение ори­гинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:

1) совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.);

2) целевую функцию (функцию цели, показатель эф­фективности, критерий оптимальности, функционал зада­чи и др.). Целевая функция позволяет выбирать наилуч­ший вариант -из множества возможных. Наилучший ва­риант доставляет целевой функции экстремальное значе­ние. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень об­служивания или дефицитности, число комплектов, отходы и т. д.;

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

Один из разделов математического программирования - линейным программированием.   Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполните­лям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспек­тивного, текущего и оперативного планирования и управ­ления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах раз­вития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного програм­мирования получили при решении задач экономии ресур­сов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспорт­ных и других задач.

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Кан­торовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в эконо­мике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (ме­тода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного пла­на;

3) умение переходить к нехудшему опорному плану.

 

§ 1. Задача линейного программирования и свойства  ее решений.

 

1.1 Понятие линейного программирования. Линейное про­граммирование—раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополни­тельных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на уни­версальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного про­граммирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.

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

 

Формы записи задачи линейного программирования:

Общей задачей линейного программирования называют задачу

(1)

при ограничениях

(2)

(3)

  (4)

(5)

- произвольные    (6)

где - заданные действительные числа; (1) – целевая функция; (1) – (6) –ограничения;

 - план задачи.

 

Свойства решений .

Пусть ЗПЛ представлена в следующей записи:

     (7)

(8)

                (9)

Чтобы задача (7) – (8) имела решение, системе её ограничений (8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r= n система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки много­гранных решений. Пусть r<n. В этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линей­ная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r век­торам базиса, называют, как известно, базисными и обо­значают БП. Остальные n – r переменных будут свобод­ными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свобод­ными будут переменные .

Если свободные переменные приравнять нулю, а базис­ные переменные при этом примут неотрицательные значе­ния, то полученное частное решение системы (8) назы­вают опорным решением (планом).

Теорема. Если система векторов  содер­жит m линейно независимых векторов , то допустимый план    (10) является крайней точкой многогранника планов.

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

Графический способ решения ЗЛП.

Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования бо­лее сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в простран­ствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практиче­ского значения, однако его рассмотрение проясняет свой­ства ОЗЛП, приводит к идее ее решения, делает геомет­рически наглядными способы решения и пути их практи­ческой реализации.

Пусть дана задача

      (11)

    (12)

                    (13)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (12), (13) задает на плоскости некоторую полуплоскость. Полу­плоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множест­вом. Отсюда следует, что область допустимых решений задачи (11) — (13) есть выпуклое множество.

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — не­пустое множество, например многоугольник .

 

 Выберем произвольное значение целевой функ­ции . Получим . Это уравнение пря­мой линии. В точках прямой NМ целевая функция сохра­няет одно и то же постоянное значение . Считая в ра­венстве (11)  параметром, получим уравнение семей­ства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Найдём частные производные целевой функции по  и

      (14)

      (15)

Частная производная (14) ((15)) функции пока­зывает скорость ее возрастания вдоль данной оси. Следо­вательно,  и — скорости возрастания  соответст­венно вдоль осей  и . Вектор  называ­ется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор — указывает направление наискорейшего убывания целевой функции. Его называют антигра­диентом.

Вектор перпендикулярен к прямым  семейства

Из геометрической интерпретации элементов ЗЛП вы­текает следующий порядок ее графического решения.

1. С учетом системы ограничений строим область до­пустимых решений

2. Строим вектор  наискорейшего возра­стания целевой функции — вектор градиентного направ­ления.

3. Проводим произвольную линию уровня  

4. При решении задачи на максимум перемещаем ли­нию уровня  в направлении вектора  так, чтобы она касалась области допустимых решений в ее крайнем по­ложении (крайней точке). В случае решения задачи на минимум линию уровня  перемещают в антиградиентном направлении

5. Определяем оптимальный план  и экстре­мальное значение целевой функции .

Симплексный метод.

Общая идея симплексного метода (ме­тода последовательного улучшения плана) для решения ЗЛП состоит

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного пла­на;

3) умение переходить к нехудшему опорному плану.

 

Пусть ЗЛП представлена системой ограничений в каноническом виде:

.

Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.

Пусть система ограничений имеет вид

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

,

 которая имеет предпочтительный вид

.

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю .

Пусть далее система ограничений имеет вид

Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему

Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные  входят в левую часть (при ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план  не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограниче­ний-равенств, не имеющих предпочтительного вида, добав­ляют искусственные переменные . В целевую функцию переменные , вводят с коэффициентом М в случае реше­ния задачи на минимум и с коэффициентом -М для за­дачи на максимум, где М - большое положительное число. Полученная задача называется М-задачей, соот­ветствующей исходной. Она всегда имеет предпочти­тельный вид.

Пусть исходная ЗЛП имеет вид

        (1)

    (2)

                  (3)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

      (4)

                 (5)

,  ,                  (6)

Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет вид

Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема. Если в оптимальном плане

             (7) 

М-задачи (4)-(6) все искусственные переменные , то план  является оптимальным планом исходной задачи (1)-(3).

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

Решение исходной задачи симплексным методом путем введения искусственных переменных  называется сим­плексным методом с искусственным базисом.

Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в кото­ром все искусственные переменные , то его первые n компоненты дают оптимальный план исходной задачи.

Теорема . Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

 

Признаки оптимальности.

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

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

 

Понятие двойственности.

Понятие двойственности рассмотрим на примере зада­чи оптимального использования сырья. Пусть на предпри­ятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья m видов в объемах единиц . Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск n видов неосновной продукции. Обозна­чим через  норму расхода сырья i-го вида на единицу j-й  продукции, - цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величи­ны задачи:  — объемы выпуска j-й продукции, обеспечи­вающие предприятию максимум выручки.

Математическая модель задачи:

                         (1)

                        (2)

                                                  (3)

Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производст­ва на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их .

Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации:

1) общую стоимость отходов сырья покупающая организация стремится мини­мизировать;

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

Эти требования форма­лизуются в виде следующей ЗЛП.

Требование 1 покупающей организации – минимизация покупки:            (4)

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

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

    (5)

По смыслу задачи оценки не должны быть отрицательными:

                     (6)

Переменные  называют двойственными оценками или объективно обусловленными оценками.

Задачи (1)-(3) и (4)-(6) называют парой взаимно двойственных ЗПЛ.

Между прямой и двойственной задачами можно установить следующую взаимосвязь:

1. Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот.

2. Коэффициенты  целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.

3. Свободные члены  ограничений прямой задачи являются коэффициентами целевой функции двойст­венной.

4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.

5. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .

6. Число ограничений прямой задачи равно числу пере­менных двойственной, а число ограничений двойствен­ной — числу переменных прямой.

7. Все переменные в обеих задачах неотрицательны.

Теорема. Для любых допустимых планов  и прямой и двойственной ЗЛП справедливо неравенство , т.е.

(7) – основное неравенство теории двойственности.

---

Дата добавления: 2021-06-02; просмотров: 90; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!