4763

Математическое программирование. Линейное программирование

Конспект

Информатика, кибернетика и программирование

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

Русский

2012-11-25

1.79 MB

500 чел.

Введение

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

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

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

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


1. ПРЕДМЕТ, ОСОБЕННОСТИ И ОБЛАСТЬ ПРИМЕНЕНИЯ

МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ЭКОНОМИКЕ.

Математическое программирование – это наука, занимающаяся разработкой и практическим применением методов наиболее эффективного (или оптимального) управления организационными системами (предприятия, фирмы, банки и др.).

Цель математического программирования – изучение и анализ систем организационного управления, отыскание в них оптимизационных задач, постановка и внедрение которых могут оправдать затраты на создание автоматических систем управления в условиях, когда имеют место ограничения технико-экономического или какого-либо другого характера.

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

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

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

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

Основные этапы решения экономических задач:

  •  идентификация проблемы (или постановка задачи);
  •  построение модели;
  •  решение поставленной задачи с помощью модели;
  •  проверка адекватности модели;
  •  реализация результатов исследования.

Рассмотрим каждый из этапов подробнее.

  1.  Постановка задачи. В начале нужно осознать задачу, четко сформулировать ее. При этом определяются объекты, которые относятся к решаемой задаче, а также ситуация, реализуемая в результате ее решения. Первоначально задачу формулируют с точки зрения заказчика. Такая постановка задачи обычно не бывает окончательной. Во время анализа исследуемой системы задача постепенно уточняется.
  2.  Построение модели. Для того, чтобы задачу можно было описать количественно и использовать при ее решении вычислительную технику, нужно произвести качественный и количественный анализ объектов и ситуаций, имеющих к ней отношение. При этом сложные объекты, разбиваются на части (элементы), определяются связи этих элементов, их свойства, количественные и качественные значения свойств, количественные и логические соотношения между ними, выражаемые в виде уравнений, неравенств и т.п. Получив достаточно строгую и логически непротиворечивую, содержательную постановку задачи, нужно построить ее математическую модель.

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

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

В самом общем виде математическая модель может быть представлена следующим образом:

максимизировать   Е=f(x,y)    (1.1)

(или минимизировать)

 

при ограничениях   gi(x,y)Rbi ,  i  =  1,…,m  (1.2)

где R – отношение вида ≤, =, ≥; Е = f(x,y)- целевая функция (технико-экономический показатель качества или эффективности функционирования изучаемого процесса или явления) модели; x - вектор управляемых переменных; y - вектор неуправляемых переменных; gi – функция потребления iго ресурса (иногда соотношение спроса-предложения), bi - величина – iго ресурса.

3. Решение поставленной задачи. Для нахождения оптимального решения задачи (1.1) – (1.2) в зависимости от вида структуры и свойств целевой функции и функций системы ограничений используют те или иные методы теории оптимальных решений – методы математического программирования. Математическое программирование представляет собой дисциплину, занимающуюся изучением экстремальных задач и разработкой методов их решения. В зависимости от свойств функций f и gi математическое программирование можно рассматривать как ряд самостоятельных дисциплин, занимающихся изучением и разработкой методов решения определенных классов задач, основными из которых являются:

  •  задачи линейного программирования;
  •  задачи нелинейного программирования;
  •  задачи целочисленного программирования;
  •  задачи параметрического программирования;
  •  задачи дробно-линейного программирования;
  •  задачи стохастического программирования;
  •  задачи динамического программирования;
  •  эвристическое программирование.

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

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

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

Во многих задачах математического программирования исходные данные зависят от некоторого параметра. Такие задачи называются задачами параметрического программирования.

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

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

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

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

5. Реализация результатов исследования. На практике данный этап является завершающим. Полученное предварительно математическое решение облекают в соответствующую содержательную форму и представляют заказчику в виде инструкций и рекомендаций.


2. ПРИНЦИПЫ ПОСТРОЕНИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ЭКОНОМИЧЕСКИХ ЗАДАЧ.

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

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

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

  1.  Для определения каких величин должна быть построена модель? Другими словами, как идентифицировать переменные (искомые величины) данной задачи?
  2.  В чем состоит цель, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?
  3.  Какие ограничения должны быть наложены на переменные, чтобы выполнились условия, характерные для моделируемой системы?

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

Рассмотрим примеры наиболее типичных содержательных постановок экономических задач и построим их математические модели.

2.1 Задача оптимального производственного планирования (или задача об использовании ресурсов)

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

Содержательная постановка задачи

Допустим, предприятие выпускает продукцию п видов. При изготовлении продукции расходуются ресурсы m видов (финансы, сырье, рабочая сила, топливо и т.п.), размеры допустимых затрат которых ограничены величинами bi (i=1, ..., m). Расход ресурса i-го вида на единицу продукции j-го вида (j=1, ..., п) составляет  единиц. Себестоимость единицы продукции j-го вида равна cj, а оптовая цена — рj. По объему выпуска продукции j-го вида установлены нижняя aj и верхняя Аj, границы. Необходимо составить план выпуска продукции по видам с учетом имеющихся ресурсов и установленных ограничений, который обеспечивал бы предприятию наивысшую прибыль (доход, рентабельность и т.п.).

Построение математической модели задачи

Обозначим через xj количество единиц продукции j-го вида, планируемое к выпуску (j=1, ..., п). Тогда суммарная прибыль f(х1, ..., хn) от реализации выпущенной предприятием продукции при плане производства (x1;...;хn) может быть представлена следующей функцией:

или в компактной форме:

.    (2.1)

При этом общий фактический расход i-го ресурса, затрачиваемый на производство ассортимента продукции в запланированном объеме, представим в виде суммы:

и не должен превышать имеющегося запаса bi, т.е.:

.   (2.2)

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

.    (2.3)

Итак, математически задача сводится к нахождению числовых значений переменных x1, ..., хn, удовлетворяющих линейным ограничениям (2.2), (2.3) и доставляющих максимум линейной функции (2.1). Соотношения (2.1) — (2.3) — математическая модель данной задачи, т.е. математическая модель исходной задачи будет иметь вид:

   (2.4)

Количество ресурсов m, их запас bi, количество переменных п, коэффициенты , cj, рj, аj, Аj определяются непосредственно из условия задачи. Рассмотрим несколько типичных примеров задач из данной группы.

Пример 2.1 Задача об использовании сырья

Небольшая фабрика изготовляет два вида красок: для наружных (Е) и внутренних (I) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн соответственно. Расходы продуктов А и В на 1 тонну соответствующих красок приведены в таблице:

Исходный продукт

Расход исходных продуктов (в тоннах) на 1 тонну краски

Максимально возможный запас продукта, тонн

краска Е

краска I

А

1

2

6

В

2

1

8

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает величину спроса на краску Е более чем на 1 тонну. Кроме того, установлено, что спрос на краску I никогда не превышает 2 тонн в сутки. Оптовые цены одной тонны красок равны: 3 тыс. грн. для краски Е, 2 тыс. грн. для краски I.

Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Переменные модели.

Так как нужно определить объемы  производства краски каждого вида, переменными в модели являются:

Х1 – суточный объем производства краски Е (в тоннах);

Х2 – суточный объем производства краски I (в тоннах).

Целевая функция модели.

Так как стоимость 1 тонны краски Е равна 3 тыс. грн., суточный доход от ее продажи в количестве Х1 тонн составит 1 тыс. грн. Аналогично доход от реализации Х2 тонн краски I составит 2 тыс. грн. в сутки. При допущении независимости объемов сбыта каждой из красок общий доход равен сумме двух слагаемых – дохода от продажи краски Е и дохода от продажи краски I.

Обозначив общий доход (в тыс. грн.) через F, можно дать следующую математическую формулировку целевой функции: определить значения (допустимые) Х1 и Х2, максимизирующие величину общего дохода:

F = 3Х1 + 2Х2.

Ограничения модели.

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

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

Фактический расход исходного продукта для производства обоих видов красок

Максимально возможный запас данного исходного продукта

Это приводит к следующим двум ограничениям:

Х1  + 2Х2 6 (для А),

1 + Х2   8 (для В).

Ограничения, моделирующие соотношения спроса на продукцию, имеют следующий смысл:

Математически эти ограничения записываются следующим образом:

Х2 - Х1    1  (соотношение величин спроса на краску I и краску Е),

Х2   2  (максимальная величина спроса на краску I).

Неявное (т.е. «подразумеваемое») ограничение заключается в том, что объемы производства продукции не могут принимать отрицательных значений. Чтобы предотвратить получение таких недопустимых решений, потребуем выполнения условия неотрицательности переменных, т.е. введем ограничения на их знак:

Х1  0  (объем производства краски Е),

Х2  0 (объем производства краски I).

Итак, математическую модель можно записать в следующем виде:

Определить суточные объемы производства (Х1 и Х2) краски Е и краски I (в тоннах), при которых достигается max F = 3Х1  + 2Х2  (целевая функция), при ограничениях:

Пример 2.2 Задача об ассортименте продукции

Пусть фирма выпускает три вида продукции. В процессе производства используется три технологических операции. Технологическая схема производства изделий видов 1, 2, 3 показана на рисунке:

Так как эти технологические операции используются фирмой и для других производственных целей, фонд рабочего времени, в течение которого операции 1, 2 и 3 могут быть применены для производства рассматриваемых изделий, ограничен предельными значениями (в сутки):

  •  для 1-й операции – 430 минут;
  •  для 2-й операции – 460 минут;
  •  для 3-й операции – 420 минут;

Изучение рынка сбыта показало, что ожидаемая прибыль от продажи одного изделия видов 1, 2, 3 составляет 3, 2 и 5 грн. соответственно.

Каков наиболее выгодный суточный объем производства каждого вида продукции?

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

Переменные модели.

Х1 – количество изделий вида 1,

Х2 – количество изделий вида 2,

Х3 -  количество изделий вида 3.

Целевая функция модели.

Так как ожидаемая прибыль от продажи одного изделия каждого вида равна соответственно 3, 2 и 5 грн., а их количество равно соответственно Х1, Х2 и Х3 штук, то величина прибыли, получаемая от реализации планируемого количества изделий каждого вида, равна соответственно 1, 2 и 3 грн. Тогда общая прибыль составит:

F = 3Х1 + 2Х2 + 5Х3


Ограничения модели
.

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

Для операции 1:

- для изделия 1го вида операция 1 длится 1 мин, следовательно, Х1 шт. изделий 1 го вида потребуют времени 1*Х1 минут;

- для изделия 2 го вида операция 1 длится 2 мин, следовательно, Х2 шт. изделий 2 го вида потребуют времени 2*Х2 минут;

- для изделия 3 го вида операция 1 длится 1 мин, следовательно, Х3 шт. изделий 3 го вида потребуют времени 1*Х3 минут.

Общее время, которое используется для производства изделий трех видов при выполнении операции 1 равно Х1 + 2Х2 + Х3 минут. Это время не должно превышать по условию 430 минут. Таким образом, математически это можно записать в следующем виде:

Х1 + 2Х2 + Х3    430.

Аналогичны рассуждения для 2-й и 3-й операций. В результате получаем для них:

1 + 0*Х2 + 2Х3    460,

Х1 + 4Х2 + 0*Х3    420.

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

Х1    0, Х2    0, Х3    0.

Итак, математическую модель можно записать в следующем виде:

Определить суточные объемы производства изделий 3-х видов Х1, Х2, Х3, при  которых достигается max F = 3Х1  + 2Х2 + 5Х3, при ограничениях:

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

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

    

где   (i=1,…,m;   j=1,…n).

Вместе с этим и себестоимость сj продукции зависит от объема производства и в первом приближении описывается функцией вида:

  

Подставляя данные выражения в (2.1) и (2.2), получаем:

.

Как видно из последних соотношений модель становится нелинейной.


2.2 Задача об оптимальном составе смеси

Довольно обширный класс задач математического программирования образуют так называемые задачи на составление смесей или задачи на использование заменителей. Задача подобного рода возникает в случае необходимости смешивания различных компонент со сходными свойствами с целью создания смеси, отвечающей определенным требованиям, или при необходимости замены в смеси одних компонент другими. Характерный пример такой задачи — составление наиболее экономичных смесей горючего для двигателей разных типов. Известно, что выпускаемые марки бензина различаются теплотворной способностью, температурой воспламенения, степенью очистки и т.п. Возникает задача составления наиболее дешевой смеси из различных марок бензина при условии, чтобы определенные количественные показатели смеси были выше (или ниже) заранее установленных величин. Аналогичной является задача на составление наиболее дешевой смеси различных сортов угля для нагрева паровых котлов и т.п.

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

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

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

Пусть хозяйство располагает п видами кормов (сено, силос, концентраты и т.д.), каждый из которых содержит в различных пропорциях m видов питательных веществ (белки, кальций, фосфор, витамины и др.). Известно, что в единице корма j-го (j=1,..., n). вида содержится аij единиц i-го питательного вещества (i=1,..., m). Минимальная суточная потребность в i-ом питательном веществе составляет bi единиц, себестоимость производства единицы корма j-го вида равна cj, а выделяемый суточный объем ограничен величиной aj. Требуется выбрать рацион — набор и количество кормов — так, чтобы количество каждого питательного вещества было не меньше требуемого, а суммарная стоимость рациона была минимальной.

Построим математическую модель данной задачи.

Обозначим через xj (j=1, ...n) количество единиц корма j-го вида, включаемого в суточный рацион. Тогда общее количество i-го питательного вещества, содержащегося в рационе 1; ...; хn), выразится суммой:

.

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

.

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

Суммарная стоимость кормов, составляющих суточный рацион, определится выражением:

Таким образом, оптимальным рационом будет такой набор 1; ...; хn) кормов, который обращает в минимум линейную функцию f при соблюдении ограничений, а математическая модель задачи о рационе будет иметь вид:

Если учесть обусловленное зоотехническими требованиями определенное соотношение в рационе объемов сочных и грубых кормов, то придется дополнить модель соответствующими ограничениями. Чтобы обеспечить разнообразие рациона, следует иметь в наличии не менее а0j единиц j-го вида корма, а в модель задачи придется включить условия:

.

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

.

В итоге математическая модель задачи о рационе примет обобщенный вид:

Пример 2.3 Задача о рационе

При откорме каждое животное ежедневно должно получить не менее 60 единиц питательного вещества А, не менее 50 ед. вещества В. Указанные питательные вещества содержат три вида корма. Содержание единиц питательных  веществ в 1 кг каждого из видов кормов приведено в таблице:

Тип вещества

Кол-во единиц питательных веществ в 1 кг корма вида

І

ІІ

ІІІ

А

1

3

4

В

2

4

2

Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена 1 кг корма 1 го вида составляет 19 грн., корма 2 го вида – 24 грн., корма 3 го вида – 25 грн.

Построим математическую модель задачи. Пусть Хi – количество корма iго вида, включаемого в дневной рацион животных, i = 1, 2, 3.

Целевая функция задачи выражает суммарные денежные затраты на составление рациона, которые должны быть минимальными:

F = 19X1 + 24X2 + 25X3  min

На переменные задачи накладываются ограничения на количественное содержание питательных веществ А и В в дневном рационе животного.

для вещества А:  X1 + 3X2 + 4X3   60,

для вещества В: 2X1 + 4X2 + 2X3   50.

Левая часть каждого из ограничений формально выражает то количество единиц соответствующего питательного вещества, которое животное фактически получит в результате составления некоторого рациона Х=(Х1, Х2, Х3). Правая же часть того же ограничения – это требуемое количество единиц соответствующего питательного вещества. Учитывая требование условия задачи: животное должно получить необходимое количество единиц питательных веществ, выбираем знак неравенств “”.

Кроме того, значения переменных Хi, i = 1, 2, 3 , не могут принимать отрицательные значения, т.е. Хi  0, i = 1, 2, 3.

Таким образом, математическая модель исходной задачи будет иметь вид:

2.3 Задача об использовании мощностей (задача о загрузке оборудования)

Предприятию задан план производства продукции по времени и номенклатуре: требуется за время T выпустить п1, п2,..., пk единиц продукции Р1, P2, ...., Pk. Продукция производится на станках S1, S2, ..., Sm. Для каждого станка известны производительность  (т.е. число единиц продукции Pj, которое можно произвести на станке Si за единицу времени) и затраты  на изготовление продукции Pj на станке Si в единицу времени.

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

Составим экономико-математическую модель задачи.

Обозначим — время, в течение которого станок Si будет занят изготовлением продукции Pj(i= 1, 2,..., m; j= 1, 2, ..., k).

Так как время работы каждого станка ограничено и не превышает Т, то справедливы неравенства:

Для выполнения плана выпуска по номенклатуре необходимо, чтобы выполнялись следующие равенства:

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

.

Затраты на производство всей продукции выразятся функцией:

.

Экономико-математическая модель задачи об использовании мощностей примет вид: найти такое решение Х=(), удовлетворяющее системе ограничений, при котором функция F принимает минимальное значение, т.е.:

2.4 Задача о раскрое материалов

На раскрой (распил, обработку) поступает материал одного образца в количестве а единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам  (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i-го способа (i=1,2, ..., п) дает аik единиц k-го изделия (k = 1,2, ..., l;).

Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.

Составим экономико-математическую модель задачи. Обозначим, xi— число единиц материала, раскраиваемых i-м способом, и х — число изготавливаемых комплектов изделий. Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то .

Требование комплектности выразится уравнениями:

Очевидно, что должны соблюдаться условия: .

Экономико-математическая модель задачи: найти такое решение Х=(), удовлетворяющее построенной системе уравнений и условию неотрицательности переменных, при котором функция F=х принимает максимальное значение, т.е.:

Пример 2.4 

Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Составить экономико-математическую модель задачи.

Построение математической модели.

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

Способ распила i

Число получаемых брусьев длиной, м

1,2

3,0

5,0

1

5

-

-

2

2

1

-

3

-

2

-

4

-

-

1

Обозначим: число бревен, распиленных i-м способом (i=1, 2, 3, 4); х — число комплектов брусьев.

Учитывая, что все бревна должны быть распилены, а число брусьев каждого размера должно удовлетворять условию комплектности, экономико-математическая модель задачи примет вид (согласно приведенной выше обобщенной форме записи математической модели задачи о раскрое материала):

Задачу о раскрое легко обобщить на случаи т раскраиваемых материалов.

Пусть каждая единица j-го материала (j = 1, 2, ..., т) может быть раскроена п различными способами, причем использование i-го способа (i = 1, 2, ... , n) дает  единиц k-го изделия (k = 1, 2, ..., l), a запас j-го материала равен единиц.

Обозначим число единиц j-го материала, раскрываемого i-м способом.

Экономико-математическая модель задачи о раскрое в общей постановке примет вид: найти такое решение Х=(), удовлетворяющее системе

и условию , при котором функция  F = х  принимает максимальное значение.

Пример 2.5

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

ЗАКАЗ

Требуемая ширина, м.

Требуемое количество рулонов

1

5

150

2

7

200

3

9

300

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

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

Переменные. 

Требуемая ширина, м.

Вариант установки режущей кромки

Минимальное количество рулонов

1

2

3

4

5

6

5

0

2

2

4

1

0

150

7

1

1

0

0

2

0

200

9

1

0

1

0

0

2

300

Потери на 1 м длины

4

3

1

0

1

2

Пусть Xj – количество стандартных рулонов, разрезаемых по варианту j, .

Целевая функция. Общие потери бумаги на 1 м длины:

F = 4Х1 + 3Х2 + Х3 + Х5 + 2Х6

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

Количество рулонов шириной 5 м: 2 + 2Х3 + 4Х4 + Х5.

Количество рулонов шириной 7 м: Х1 + Х2 + 2Х5.

Количество рулонов шириной 9 м: Х1 + Х3 + 2Х6.

Каждое из этих соотношений определяет количество фактически полученных нестандартных рулонов, которое должно быть не меньше 150, 200, 300 для рулонов 5, 7 и 9 м соответственно.

На переменные задачи накладываются еще ограничения неотрицательности.

Итак, математическая модель в общем виде запишется:

min F = 4Х1 + 3Х2 + Х3 + Х5 + 2Х6 , при ограничениях

       2  + 2Х3 + 4Х4  + Х5     150   

Х1 + Х2          + 2Х5      200

Х1      + Х3    + 2Х6   300  

Хj  0,

Рассмотрим модификацию или, в некотором смысле, обобщение предыдущих задач на следующем примере.

Пример 2.6

Имеется три технологических процесса для выделения из руды двух нужных веществ А и В. Из каждой тонны руды при применении процессов I, II и III  получается, соответственно, 0,4 и 0,6; 0,6 и 0,5; 0,2 и 0,2 килограммов вещества А и В, и при этом затраты составляют: 5 тыс. грн. для процесса I, 6 тыс. грн., для процесса II и 1 тыс. грн., для процесса III. Определить оптимальное распределение 10 т руды по процессам I, II и III, минимизирующее затраты, если необходимо получить не менее 4 кг каждого вещества.


Переменные.
 

Пусть Xj – количество тонн руды, направляемых на переработку по j-му процессу,. .

Целевая функция. Целью данной задачи является минимизация суммарных затрат на применение трех технологических процессов по переработке руды. Учитывая затраты на переработку 1 тонны руды по каждому из процессов и план переработки руды, т.е. планируемое распределение руды, суммарные затраты можно выразить функцией:

.

Ограничения. В рассматриваемом примере существенными являются три ограничения на допустимые значения переменных модели:

  1.  Условие распределения 10 тонн руды между технологическими процессами переработки: .
  2.  Условия выделения из руды минимального количества веществ А и В:
    •  для вещества А: ;
    •  для вещества В: .
  3.  Условие неотрицательности переменных модели: .

Таким образом, математическая модель исходной задачи будет иметь вид:

2.5 Задача об оптимальном плане перевозок

Эту задачу часто называют транспортной. В простейшем варианте транспортная задача возникает при необходимости наиболее рациональной перевозки некоторого однородного груза. При этом потребителям безразлично, из каких пунктов он поступает, лишь бы был удовлетворен спрос, а каждый поставщик имеет возможность доставлять груз любому потребителю. Обратные перевозки не предусматриваются. Итак, пусть в m пунктах производится соответственно a1,…,am единиц некоторого продукта, потребности в котором в n пунктах выражаются величинами b1,…,bn единиц (предполагается, что общий спрос на продукт не превышает возможностей производства, т. е. ).

Известны затраты cij по перевозке единицы продукта из i-го пункта производства в j-й пункт потребления. Требуется составить наиболее экономный план перевозок (в смысле суммарных транспортных расходов), обеспечивающий удовлетворение всех потребностей в продукте.

Построим математическую модель данной задачи.

Обозначим через хij количество продукта, перевозимого из i-го пункта производства в j-й пункт потребления. Тогда  задача  сводится к определению числовых значений mn неизвестных хij (i=1, ..., m;  j=1, ..., n), удовлетворяющих условиям:

 

(из каждого пункта производства вывозится не более производимого в нем количества продукта);

 

(в каждый пункт потребления доставляется не менее требуемого им количества продукта);

 (i=1, ..., m;  j=1, ..., n) (перевозимое количество продукта обратно в пункт производства не возвращается) и доставляющих минимум функции  (суммарные затраты на перевозки  продукта).       


2.6 Задача об оптимальном размещении производства

Это одна из важных модификаций транспортной задачи. Допустим, что в m пунктах имеются или могут быть размещены; предприятия, производящие некоторый продукт. Затраты по производству единицы продукта в i-м пункте (i=1, ..., m) равны сi, а возможный максимальный объем производства составляет аi, единиц. Потребность в продукте в n пунктах выражается величинами  b1,…,bn единиц. Стоимость доставки единицы продукта с i-го предприятия j-му потребителю равна cij единиц. Требуется так выбрать места расположения новых предприятий, объемы xi производства в них и план перевозок, чтобы суммарные затраты по выпуску и перевозке необходимого объема продукта были минимальными.

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

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

Если учесть, что производственные затраты зависят от объема хi выпуска нелинейно и описываются на i-м предприятии функцией fi(xi), то целевая функция (при упрощающем условии, что производственные мощности не ограничены) примет вид: , и задача станет нелинейной.

2.7 Сельскохозяйственные задачи

Отрасль применения математических методов, а именно методов линейного программирования, в сельском хозяйстве весьма широка. С помощью методов линейного программирования решаются такие задачи:

  1.  Выбор наилучшей структуры посевных площадей.
  2.  Выбор оптимальных размеров хозяйств разных форм собственности.
  3.  Рациональное размещение капиталовложений.
  4.  Определение оптимального набора машин в хозяйстве.
  5.  Определение оптимального рациона в животноводстве (задача составления кормовой смеси).
  6.  Подбор наилучшей структуры удобрений.
  7.  Специализация хозяйств и т.д.

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

Пример 2.7 

Сельскохозяйственное предприятие выделило три земельных массива площадью 5, 8 и 9 тыс. га соответственно под посевы ржи, пшеницы и кукурузы. Средняя урожайность культур на каждом массиве указана в таблице:

Культура

Урожайность земельного массива

первого

второго

третьего

Рожь, ц/га

20

18

17

Пшеница, ц/га

30

25

28

Кукуруза, ц/га

25

24

26

За 1ц. ржи хозяйство получает 20 у.д.е. (условных денежных единиц), за 1ц. пшеницы — 25 у.д.е. и за 1ц. кукурузы — 14 у.д.е.

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

Математическая постановка задачи

Обозначим через х1 (га) площадь, которая отводится под рожь на первом массиве, через х2 (га) площадь, которая отводится под рожь на втором массиве, через х3 (га) площадь, которая отводится под рожь на третьем массиве.

Аналогично через х4, х5, х6 (га) обозначим соответственно площадь под пшеницу на первом, втором и третьем массивах и через х7, х8, х9 (га) — площадь под кукурузу на первом, втором и третьем массивах.

Составим систему уравнений:

Учитывая урожайность каждой культуры на каждом с массивов, и взяв во внимание план, получим такие три ограничения:

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

Необходимо найти такие положительные значения х1, х2, .., х9,  которые удовлетворяют уравнениям и неравенствам системы и доставляют целевой функции максимум.

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

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


3 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

3.1 Постановка и различные формы представления задач линейного программирования

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

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

Общей задачей ЛП называется задача, которая состоит в определении максимального (минимального) значения функции:

    (3.1)

при условиях:


   (3.2)

  (3.3)

   (3.4)

где aij , bi, cj - заданные постоянные величины и k  m.

Функция (3.1) называется целевой функцией задачи (3.1) – (3.4), а условия (3.2) – (3.4) – ограничениями данной задачи.

Различают еще две основные формы задач ЛП в зависимости от наличия ограничений разного типа: стандартную и каноническую.

Стандартной (или симметричной) ЗЛП называется задача, которая состоит в определении максимального значения функции (3.1) при выполнении условий (3.2) и (3.4), где k = m , и l=n, т.е.

 

  (3.5)

Канонической (или основной) ЗЛП называется задача, которая состоит в определении максимального значения целевой функции (3.1) при выполнении условий (3.3) и (3.4), где k=0, и l=n, т.е.

 

  (3.6)

 

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

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

Чтобы перейти от одной формы записи ЗЛП к другой нужно уметь:

  1.  сводить задачу минимизации функции к задаче максимизации;
  2.  переходить от ограничений – неравенств к ограничениям – равенствам;
  3.  заменять переменные, которые не подчинены условию неотрицательности, на неотрицательные переменные.
  4.  В том случае, когда требуется найти min функции F=c1x1+c2x2+…+cnxn, можно перейти к нахождению максимума функции F1, умножив коэффициенты при переменных в целевой функции модели на (-1), т.е.:

F1 = - F = - c1x1 - c2x2 - ……- cnxn , т.к.  min F  = - max (- F).

  1.  Ограничение – неравенство исходной задачи ЛП можно преобразовать в ограничение – равенство добавлением к его левой части неотрицательной переменной с соответствующим знаком.

Таким образом, ограничение – неравенство вида

преобразуется в ограничение – равенство

,

а ограничение – неравенство  вида  

в ограничение – равенство

.

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

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

  1.  Если переменная Хк не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными , приняв . Правомерность такой замены очевидна, т.к. любое число можно представить в виде разности двух неотрицательных чисел.

3.2 Свойства основной задачи линейного программирования. Геометрическая интерпретация задачи линейного программирования

В ЛП сложилась определенная терминология, которой мы и будем придерживаться.

Совокупность чисел – вектор Х = (х1, х2, …..,хn), удовлетворяющих ограничениям задачи (3.2) – (3.4), называется допустимым решением.

Допустимое решение , при котором целевая функция задачи (3.1) принимает свое максимальное (минимальное) значение, называется оптимальным решением.

Запишем задачу ЛП, представленную в канонической форме, в векторной форме:

  (3.7)

где С = (с1, с2,…,сn), Х = (х1, х2…,хn), СХ - скалярное произведение векторов, Р1,…..Рn, Роm-мерные вектор – столбцы, составленные из коэффициентов при неизвестных и свободных членов системы уравнений задачи:

.

Решение  Х = (х1, х2,…..хn)  канонической задачи (3.7) называется опорным планом, если система векторов Pj, соответствующих положительным компонентам Xj, линейно независима.

Так как векторы Рj являются  m – мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше чем m . Остальные его  (n-m) компонент равны нулю.

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

Свойства основной задачи ЛП (3.7) тесным образом связаны со свойствами выпуклых множеств.

Пусть Х1, Х2,…..Хn  - произвольные точки евклидова пространства En. Выпуклой линейной комбинацией этих точек называется сумма

1 х1  + 2 х2 + …… + n xn ,

где i – произвольные неотрицательные числа, сумма которых равна 1:

  i   0,  

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

Свойства основной задачи ЛП

Теорема 3.1 Множество планов  основной задачи ЛП является выпуклым (если оно не пусто).

Непустое множество планов основной задачи ЛП называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

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

Теорема 3.3 Если система векторов  Р1 , Р2,…..Рk, (k n)  в разложении  линейно независима и такова, что , где все хi0, то точка Х=(х1, х2,…..хк,, 0,…., 0) является вершиной многогранника решений.

Теорема 3.4 Если Х = (х1, х2,…..хn) – вершина многогранника решений, то векторы Рj, соответствующие положительным xj в разложении , линейно независимы.

Геометрическая интерпретация ЗЛП

Сформулированные теоремы позволяют сделать следующие выводы.

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

Геометрическая интерпретация ЗЛП позволяет разработать и в некоторых случаях использовать (в случае, когда n-m=2, где n – количество переменных в задаче, m – число линейно независимых ограничений в системе ограничений ЗЛП) несложный метод ее решения – графический метод.


3.3 Графический метод решения ЗЛП

Рассмотрим сначала простейший случай, когда в ЗЛП включены ровно две переменные:

  (3.8)

Каждое из неравенств (a)-(b) системы ограничений задачи (3.8) геометрически определяет полуплоскость соответственно с граничными прямыми , Х1=0 и Х2=0. Каждая из граничных прямых делит плоскость х1Ох2 на две полуплоскости. Все решения исходного неравенства лежат в одной из образованных полуплоскостей (все точки полуплоскости) и, следовательно, при подстановке координат любой ее точки в соответствующее неравенство обращает его в верное тождество. С учетом этого и определяется та полуплоскость, в которой лежат решения неравенства, т.е. путем выбора любой точки из какой-либо полуплоскости и подстановки ее координат в соответствующее неравенство. Если неравенство выполняется для данной точки, то оно выполняется и для любой другой точки из этой же полуплоскости. В противном случае решения неравенства лежат в другой полуплоскости.

В том случае, если система неравенств (a)-(b) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то область допустимых решений задачи (3.8) является выпуклое множество, которое называется многоугольником решений (введённый ранее термин “многогранник решений” обычно употребляется, если n3). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

Таким образом, исходная ЗЛП состоит в нахождении такой точки многоугольника решений, в которой целевая функция F принимает максимальное (минимальное) значение.

Эта точка существует тогда, когда многоугольник решений не пуст и на нём целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины строят линию уровня L: c1x1+c2x2=h (где h – некоторая постоянная), перпендикулярную вектору-градиенту и проходящую через многоугольник решений, и передвигают её параллельно вдоль вектора-градиента  до тех пор, пока она не пройдёт через последнюю её общую точку пересечения с многоугольником решений (при построении вектора-градиента откладывают точку (с1; с2) в плоскости х1Ох2 и проводят к ней из начала координат направленный отрезок). Координаты указанной точки и определяют оптимальный план данной задачи.

Суммируя все выше изложенное, приведем алгоритм графического метода решения ЗЛП.

Алгоритм графического метода решения ЗЛП

  1.  Построить многоугольник решений, задаваемый системой ограничений исходной ЗЛП.
  2.  Если построенный многоугольник решений – пустое множество, то исходная ЗЛП решений не имеет. В противном случае построить вектор-градиент  и провести произвольную линию уровня L, перемещая которую при решении задачи на максимум в направлении вектора  (или в обратном направлении для задачи на минимум) определить крайнюю точку многоугольника решений, где и достигается максимум (минимум) целевой функции задачи.
  3.  Вычислить координаты найденной оптимальной точки , решив систему уравнений двух граничных прямых, пересекающихся в ней.
  4.  Подстановкой найденного оптимального решения  в целевую функцию задачи вычислить оптимальное ее значение, т.е.: .

При графическом построении множества допустимых решений ЗЛП (многоугольника решений) возможны следующие ситуации:

  1.  Множество допустимых решений – замкнутый многоугольник:
    1.  оптимальное решение достигается в единственной точке:

точка А – точка максимума, точка В – точка минимума;

  1.  оптимальное решение достигается во всех точках грани (отрезка) многоугольника:

все точки отрезка АВ – оптимальные решения ЗЛП (точки максимума); максимальное значение целевой функции в этом случае находится подстановкой координат любой из этих точек в целевую функцию исходной задачи.

  1.  Множество допустимых решений – незамкнутый многоугольник:

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

  1.  Множество допустимых решений – пустое множество:

Данная ЗЛП решений не имеет.

Рассмотрим теперь случай, когда n-m=2, т.е. число переменных больше числа линейно независимых уравнений на 2.

Две из n переменных, например, x1 и х2, можно выбрать в качестве свободных, а остальные m сделать базисными и выразить их через свободные:

    (3.9)

где  - константы, полученные после алгебраических преобразований системы ограничений задачи (3.6), записанной в канонической форме, к виду (3.9).

Учитывая условия неотрицательности переменных: , систему равенств (3.9) можно записать в виде:

   (3.10)

Подставляя в целевую функцию задачи (3.6) выражения (3.10) для базисных переменных, получим ЗЛП, приведенную к виду (3.8):

   (3.11)

где  - коэффициенты при переменных в целевой функции исходной ЗЛП после преобразования (3.10).

Задача (3.11) решается с помощью описанного выше алгоритма.

Рассмотрим примеры решения ЗЛП графическим методом для техническо-экономических задач, математические модели которых были построены в разделе 2.


Пример 3.1 Задача об использовании сырья
(пример 2.1, раздел 2)

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

Математическая модель данной задачи содержит ровно n=2 переменные. Решаем ее с помощью описанного выше алгоритма.

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

Заменяем условно знаки неравенства на знаки равенства и строим многоугольник решений, ограниченный прямыми (для построения прямой выбираем произвольные две точки, удовлетворяющие ее уравнению):

  1.  : (0; 3), (6; 0);
  2.  : (3; 2), (4; 0);
  3.  : (0; 1), (2; 3);
  4.  ;
  5.  .

Пятиугольник АВСDО – искомая область допустимых решений. Максимальное значение целевая функция задачи достигает на границе данного пятиугольника: либо в одной из его вершин, либо на одной из его граней. Чтобы выяснить этот вопрос, строим вектор-градиент , проводя направленный отрезок из начала координат в точку (3; 2), и перпендикулярную ему произвольную линию уровня L, перемещая которую по направлению вектора , находим крайнее положение, которое она займет в пересечении с областью допустимых решений АВСDО. Как видно из рис. 3.1, крайнее положение линия уровня займет в точке С, т.е. в данной точке целевая функция задачи достигает своего максимального значения на заданном множестве допустимых решений.

Координаты точки С вычисляем, решая систему уравнений прямых (1)-(2), пересекающихся в данной точке, т.е.:

, откуда .

Тогда максимальное значение целевой функции исходной задачи будет равно:

.


Пример 3.2 Задача о распределении руды  
(пример 2.6, раздел 2)

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

Данная задача содержит n>2 переменных. Поэтому преобразуем сначала неравенства системы ограничений задачи к равенствам, введя в левые части 2-го и 3-го ограничений дополнительные переменные х4 и х5 соответственно. Получим задачу:

Преобразованная ЗЛП имеет 3 линейно независимых ограничения-равенства (m=3) и 5 переменных (n=5), т.е. число свободных переменных задачи (k=n-m) равно 2. Значит, выразив базисные переменные х3, х4 и х5 через свободные переменные х1 и х2, получим:

После подстановки х3 в целевую функцию, 2-е и 3-е ограничения будем иметь задачу:

Учитывая условие неотрицательности переменных: , можно записать:

или

Последняя задача содержит ровно n=2 переменные и может быть решена графическим методом.

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

Заменяем условно знаки неравенства на знаки равенства и строим многоугольник решений, ограниченный прямыми (для построения прямой выбираем произвольные две точки, удовлетворяющие ее уравнению):

  1.  : (0; 10), (10; 0);
  2.  : (0; 5), (10; 0);
  3.  : (5; 0), (0; 20/3);
  4.  .

Четырехугольник АВСD – искомая область допустимых решений. Минимальное значение целевая функция задачи достигает на границе данного четырехугольника: либо в одной из его вершин, либо на одной из его граней. Чтобы выяснить этот вопрос, строим вектор-градиент (для удобства построения и наглядности рисунка значения координат вектора-градиента удвоены) , проводя направленный отрезок из начала координат в точку (8; 10) и перпендикулярную ему произвольную линию уровня L, перемещая которую в направлении, обратном вектору  (для задачи на минимум), находим крайнее положение, которое она займет в пересечении с областью допустимых решений АВСD. Как видно из рис. 3.2, крайнее положение линия уровня займет в точке С, т.е. в данной точке целевая функция задачи достигает своего минимального значения на заданном множестве допустимых решений.

Координаты точки С вычисляем, решая систему уравнений прямых (2)-(3), пересекающихся в данной точке, т.е.:

, откуда .

Тогда минимальное значение целевой функции задачи будет равно:

.

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

Таким образом, окончательно можно записать:

.


3.4 Решение задачи линейного программирования табличным симплексным методом

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

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

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

Рассмотрим задачу, для которой этот план можно непосредственно записать.

Пусть исходная задача приведена к каноническому виду (3.6):

F = c1x1 + c2x2 + ……+ cnxn max   (3.12)

……………………………………… .  (3.13)

Здесь aij, bi, ci  () - заданные постоянные числа (mn, bi  0). Говорят, что система уравнений, записанная в форме (3.13), имеет предпочтительный вид.

Векторная форма данной задачи имеет следующий вид:

    (3.14)

(3.15)

где ; .

Так как , то по определению опорного плана  является опорным планом данной задачи.

Этот план определяется системой единичных векторов Рn+1n+2,….. Рn+m, которые образуют базис m-  мерного пространства.

Алгоритм табличного симплексного метода

  1.  Построение начального опорного плана:
  2.  Приведение задачи к каноническому виду.
  3.  Приведение системы ограничений к предпочтительному виду (3.13).
  4.  Построение первой симплекс- таблицы:

а) в столбце «Базис» записываются базисные переменные Хn+1,…, Хn+m (если некоторые или все переменные  Хn+1,…, Хn+m, не входят в целевую функцию, то их коэффициенты равны нулю);

б) в столбце Сб записываются коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и переменные данного базиса;

в) в столбце Ро записываются свободные члены b1, b2,…, bm системы ограничений в предпочтительном виде;

г) на пересечении последних (n+m) столбцов и первых m строк расположена матрица коэффициентов системы ограничений;

д) в индексной строке (m+1я строка) располагают коэффициенты и , рассчитанные как скалярные произведения соответствующих векторов: .

  1.  Проверка условия оптимальности:

а) все , - данный опорный план является оптимальным;

б)  для некоторого j , и все соответствующие этому индексу величины аij0,, - функция неограниченная сверху:

в)  для некоторого j, и для каждого такого j по крайней мере одно из чисел  аij>0, тогда можно перейти от исходного опорного плана к новому опорному плану, при котором значение целевой функции увеличится.

II. Переход к лучшему опорному плану (см. таблицу).

  1.  Выбор разрешающего столбца:

для всех выбирается , для выбранного  в базис вводят соответствующую переменную Xk.

  1.  Выбор разрешающей строки:

Для разрешающего столбца  определяют  (aik > 0): выбранная строка с индексом r определяет переменную хr , которую необходимо вывести из базиса.

  1.  Выбор разрешающего элемента: это элемент, стоящий на пересечении строки с индексом r и столбца с индексом k: аrk.
  2.  Симплексные преобразования и построение второй симплекс-таблицы:

а) столбец «Базис»: переменная Xr заменяется на Xk, остальные переменные не меняются;

б) Сб заполняется соответствующими коэффициентами при базисных переменных в целевой функции;

в) элементы разрешающей строки делятся на разрешающий элемент и записываются в соответствующей по номеру строке новой таблицы;

г) элементы разрешающего столбца равны нулю, за исключением элемента, соответствующего месту разрешающего элемента. Он равен 1.

д) все остальные элементы новой таблицы рассчитываются по формулам:

 , при i≠r  (3.16)

где , bi- элементы новой симплекс-таблицы, aij, bi - элементы предыдущей симплекс-таблицы, ark - разрешающий элемент, aik - элемент разрешающего столбца, br, arj - элементы разрешающей строки.

  1.  Проверка условий оптимальности (I.4) и либо переход к (II), либо конец.

i

Базис

Сб

Ро

С1

С2

Сr

Сk

Сn

Сn+1

Сn+2

Сn+m

X1

X2

Xr

Xk

Xn

Xn+1

Xn+2

Xn+m

1

Xn+1

Cn+1

b1

a11

a12

.

a1r

.

a1k

.

a1n

1

0

.

0

2

Xn+2

Cn+2

b2

a12

a22

.

a2r

.

a2k

.

a2n

0

1

.

0

.

….

….

.

.

.

.

r

Xn+r

Cn+r

br

ar1

ar2

.

arr

.

ark

.

arn

.

….

.

….

….

.

.

.

.

m

Xn+m

Cn+m

bm

am1

am2

.

amr

.

amk

.

amn

0

0

.

1

m+1

o

1

2

.

r

.

k

.

n

0

0

.

0

Примечание. Для каждой симплексной таблицы можно записать текущий опорный план по следующему правилу: значение базисных переменных записаны в соответствующих ячейках столбца Ро, а небазисные переменные равны нулю. Кроме того, в ячейке записано текущее значение целевой функции при текущем опорном плане задачи. В последней таблице (для которой ), в указанных ячейках будет записан оптимальный план  и максимальное значение целевой функции Fmax(X*).

Пример 3.3

Рассмотрим задачу об использовании сырья (пример 2.1)

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

F = 3x1 + 2x2 max,

x1    + 2x2 6

2x1 + x2     8

- x1 + x2    1

   x2    2

x1, x20

Приведем данную модель к каноническому виду.

  1.  Целевая функция удовлетворяет требованию максимизации, т.е. соответствует каноническому виду.
  2.  Система ограничений представляет собой систему неравенств типа «≤». Приводим ее к системе ограничений-равенств путем введения в каждое из неравенств неотрицательной дополнительной переменной с коэффициентом «+1»:

x1 + 2x2 + x3   =6,

2x1 + x2         +x4 =8,

-x1 + x2  +x5  =1,

   x2             +x6  =2.

Дополнительные переменные имеют определенный экономический смысл. Для данной задачи дополнительные переменные х3 и х4 отражают расход и наличие производственных ресурсов (т.е. продуктов А и В соответственно), а их числовое значение в плане задачи равно объему неиспользованного соответствующего ресурса; дополнительные переменные х5 и х6 характеризуют величину дисбаланса между планируемым объемом производства и величиной спроса.

  1.  Согласно экономическому содержанию все переменные задачи могут принимать только неотрицательные значения, т.е.  xj0, .

Таким образом, исходная задача приведена к канонической форме. Система ограничений имеет вид:

F=3x1+2x2max,

х1   + 2x2 + x3  =6

2x1 + x2     +  x4  =8

-x1 + x2   +x5 =1

   x2        +x6=2

хj0, .

Начальный опорный план данной задачи образуют m=4 единичных вектора: Р3=(1 0 0 0 ), Р4=(0 1 0 0 ), Р5=(0 0 1 0 ), Р6=(0 0 0 1 ), соответствующие, в данном случае, дополнительным переменным х3, х4, х5, х6.

Составляем первую симплекс-таблицу.

і

Базис

Сб

Р0

3

2

0

0

0

0

Х1

Х2

Х3

Х4

Х5

Х6

1

Х3

0

6

1

2

1

0

0

0

2

Х4

0

8

2

1

0

1

0

0

3

Х5

0

1

-1

1

0

0

1

0

4

Х6

0

2

0

1

0

0

0

1

5

0

-3

-2

0

0

0

0

В столбец «Базис» заносим наименование базисных переменных, соответствующих начальному опорному плану.

В столбец «Сб» заносятся коэффициенты при базисных переменных в целевой функции задачи. Так как переменные Х3, Х4, Х5, Х6 отсутствуют в целевой функции, то их коэффициенты равны нулю.

В столбец «Р0» заносится столбец свободных членов в системе ограничений.

На пересечении первых 4-х строк и последних 6-ти столбцов, соответствующих переменным задачи, записываем матрицу коэффициентов при неизвестных в системе ограничений.

Элементы индексной строки (5-я строка) заполняются для столбцов Р0 и Х1, …, Х6:

  •  для столбца Р0: 0=Сб0, т.е.  0=0*6+0*8+0*1+0*2=0;
  •  для столбца Хj, j=1,6 : j= Сбjj

где Рj – вектор-столбец коэффициентов при переменной Хj в системе ограничений, сj – коэффициент при Хj в целевой функции задачи.

Например, 1 = 0*1 + 0*2 + 0*(-1) + 0*0 – 3 = -3;

2 = 0*2 + 0*1 + 0*1 + 0*1 - 2 = -2.

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

Построенная симплекс-таблица характеризует начальный опорный план задачи: Х0=(0; 0; 6; 8; 1; 2).

Значения базисных переменных взяты из столбца Р0, все небазисные переменные, - Х1 и Х2, - равны нулю.

Значение целевой функции при данном плане равно: F(x0)=0 (значение ячейки таблицы 0).

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

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

Так как 1 = -3 < 0 и 2 = -2 < 0, то план Х0 не оптимальный. Переходим к лучшему плану, выбрав разрешающие столбец и строку.

Разрешающий столбец выбираем из условия:

.

Таким образом, в новый базис необходимо ввести переменную Х1 соответствующую 1.

Для положительных элементов разрешающего столбца рассчитываем:

.

Данное соотношение определяет разрешающую строку, т.е. ту переменную, которую необходимо вывести из базиса (в нашем случае это Х4).

Разрешающий элемент a21=2.

Согласно пунктам 4а)-д) алгоритма заполняем новую симплекс-таблицу и проверяем ее на оптимальность.

і

Базис

Сб

Р0

3

2

0

0

0

0

Х1

Х2

Х3

Х4

Х5

Х6

1

Х3

0

2

0

3/2

1

-1/2

0

0

2

Х1

3

4

1

½

0

½

0

0

3

Х5

0

5

0

3/2

0

½

1

0

4

Х6

0

2

0

1

0

0

0

1

5

12

0

-1/2

0

3/2

0

0

Для переменных нового базиса в соответствующем столбце на пересечении одноименных переменных ставится «1», остальные элементы столбца – «0».

Элементы второй строки новой таблицы (соответствующей разрешающей строке предыдущей таблицы) получаем путем деления элементов разрешающей строки на разрешающий элемент.

Все остальные элементы таблицы пересчитываем по формулам (3.16).

Например элемент 1й строки столбца Р0:

,

или элемент 3-й строки 2-го столбца:

 и т.д.

Таким образом, новый опорный план задачи Х1 = (4; 0; 2; 0; 5; 2) предусматривает выпуск 4 тонн краски Е (Х1=4), краска I не выпускается (Х2=0), продукт В полностью израсходован (Х4=0), а остаток продукта А – 2 тонны (Х3=2); дисбаланс между выпуском красок 5 тонн (Х5=5), а спрос на краску I превышает предложение, т.е. ее выпуск на 2 тонны (Х6=2).

При таком плане производства фирма получает прибыль, равную F(Х1)=12 тыс. грн.

Построенный план не оптимален, так как 2 = -1/2 < 0.

Переходим к лучшему опорному плану, введя в новый базис переменную Х2 вместо переменной Х3:

.

Элемент а12 = 3/2 – разрешающий элемент.

Строим новую симплекс-таблицу согласно пунктам 4а)-д) алгоритма:


і

Базис

Сб

Р0

3

2

0

0

0

0

Х1

Х2

Х3

Х4

Х5

Х6

1

Х2

2

4/3

0

1

1

-1/3

0

0

2

Х1

3

10/3

1

0

0

2/3

0

0

3

Х5

0

3

0

0

0

1

1

0

4

Х6

0

2/3

0

0

0

1/3

0

1

5

38/3

0

0

0

4/3

0

0

В последней симплексной таблице все j0, . Значит, соответствующий ей план является оптимальным, т.е. , .

Таким образом, оптимальный план производства предусматривает выпуск 10/3 тонн краски Е и 4/3 тонн краски I, прибыль от реализации которой будет максимальной и составит  тыс. грн. При данном плане производства продукты А и В полностью израсходованы; дисбаланс между объемом производства красок I и Е составляет 3 тонны/день, а спрос на краску I не удовлетворен на 2/3 тонны/день.


3.5 Метод искусственного базиса решения задачи линейного программирования

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

Рассмотрим такую задачу.

Пусть требуется найти максимум функции:

F = c1x1 + c2x2 + ……+ cnxn      (3.17)

при условиях:

   (3.18)

где bi  0 (), m<.n и среди векторов P1, P2, …, Pn нет m единичных.

Задача, состоящая в определении максимального значения функции:

F = c1x1 + c2x2 + ……+ cnxn xn+1- …- Мxn+m    (3.19)

при условиях:

  (3.20)

где M — некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей по отношению к задаче (3.17) - (3.18).

Расширенная задача имеет опорный план: Х=(0; 0; ...; 0; b1; b2; ...;bm), определяемый системой единичных векторов Pn+1; Рп+2, … Рп+т, которые образуют базис m-мерного векторного пространства, называемого искусственным. Сами векторы, так же как и переменные xn+i (), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.

Теорема 3.5 Если в оптимальном плане X*=(x*1, x*2, ...; x*n, x*n+1; ...; x*n+m) расширенной задачи (3.19) - (3.20) значения искусственных переменных x*n+i=0 (), то X*=(x*1, x*2, ...; x*n) является оптимальным планом задачи (3.17) - (3.18).

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

Примечание. Расширенная задача решается с помощью описанного в п.3.4 алгоритма табличного симплекс-метода. На практике для удобства его использования в расширенной задаче конкретизируют коэффициенты М при искусственных переменных xn+i () в целевой функции задачи, присваивая им значения, на порядок превышающие значение любого из коэффициентов при остальных переменных в целевой функции задачи. После чего такая задача решается с помощью обычных симплексных преобразований.

Итерационный процесс ведут до тех пор, пока:

  1.  либо все искусственные векторы не будут исключены из базиса;
  2.  либо не все искусственные векторы исключены, но индексная строка не содержит больше отрицательных элементов среди оценок оптимальности 1, …, ∆n.

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

Этапы нахождения решения ЗЛП методом искусственного базиса:

  1.  Составляют расширенную задачу (3.19) - (3.20).
  2.  Находят опорный план расширенной задачи.
  3.  С помощью обычных вычислений симплекс-метода исключают искусственные переменные из базиса. В результате либо находят опорный план исходной задачи (3.17) — (3.18), либо устанавливают ее неразрешимость.
  4.  Используя найденный опорный план задачи (3.17) — (3.18), либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.

Рассмотрим пример решения ЗЛП методом искусственного базиса для задачи, математическая модель которой была построена в разделе 2 (пример 2.6).

Пример 3.4 Задача о распределении руды

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

Запишем данную задачу в канонической форме:

В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:

Среди векторов P1, Р2, … P5 нет единичных. Поэтому в левую часть каждого уравнения системы ограничений задачи вводим искусственные неотрицательные переменные х6 - х8 и рассмотрим расширенную задачу:

Расширенная задача имеет опорный план Х=(0; 0; 0; 0; 0; 10; 4; 4), определяемый системой трех единичных векторов: P6, P7, Р8:

.

Для решения расширенной задачи с помощью симплексного метода примем значение М=100. Тогда окончательно получаем ЗЛП, пригодную для применения алгоритма симплексного метода:

Решение оформим последовательностью симплекс-таблиц:

Базис

Сб

Р0

-5

-6

-1

0

0

-100

-100

-100

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х6

-100

10

1

1

1

0

0

1

0

0

Х7

-100

4

0,4

0,6

0,2

-1

0

0

1

0

Х8

-100

4

0,6

0,5

0,2

0

-1

0

0

1

 

 

-1800

-195

-204

-139

100

100

0

0

0

Х1=(0; 0; 0; 0; 0; 10; 4; 4), - не оптимальный, F11)=-1800.

Базис

Сб

Р0

-5

-6

-1

0

0

-100

-100

-100

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х6

-100

3,333

0,33

0

0,7

1,67

0

1

-1,7

0

Х2

-6

6,667

0,67

1

0,3

-1,7

0

0

1,67

0

Х8

-100

0,667

0,27

0

0

0,8

-1

0

-0,8

1

 

 

-440

-59

0

-71

-240

100

0

340

0

Х2=(0; 6,667; 0; 0; 0; 3,333; 0; 0,667), - не оптимальный, F12)=-440.

Базис

Сб

Р0

-5

-6

-1

0

0

-100

-100

-100

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х6

-100

2

-0,2

0

0,6

0

2

1

0

-2

Х2

-6

8

1,2

1

0,4

0

-2

0

0

2

Х4

0

0,8

0,32

0

0

1

-1,2

0

-1

1,2

 

 

-248

17,8

0

-61

0

-188

0

100

288

Х3=(0; 8; 0; 0,8; 0; 2; 0; 0), - не оптимальный, F13)=-248.

Базис

Сб

Р0

-5

-6

-1

0

0

-100

-100

-100

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х5

0

1

-0,1

0

0,3

0

1

0,5

0

-1

Х2

-6

10

1

1

1

0

0

1

0

0

Х4

0

2

0,2

0

0,4

1

0

0,6

-1

0

 

 

-60

-1

0

-5

0

0

94

100

100

Х4=(0; 10; 0; 2; 1; 0; 0; 0), - не оптимальный, F14)=-60.

Базис

Сб

Р0

-5

-6

-1

0

0

-100

-100

-100

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х3

-1

3,333

-0,3

0

1

0

3,3

1,7

0

-3,3

Х2

-6

6,667

1,33

1

0

0

-3,3

-0,7

0

3,3

Х4

0

0,667

0,33

0

0

1

-1,3

-0,1

-1

1,3

 

 

-43,3

-2,7

0

0

0

17

102

100

83

Х4=(0; 6,667; 3,333; 0,667; 0; 0; 0; 0), - не оптимальный, F14)=-43,3.

Базис

Сб

Р0

-5

-6

-1

0

0

-100

-100

-100

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х3

-1

4

0

0

1

1

2

1,6

-1

-2

Х2

-6

4

0

1

0

-4

2

-0,4

4

-2

Х1

-5

2

1

0

0

3

-4

-0,2

-3

4

 

 

-38

0

0

0

8

6

102

92

94

Х5=(2; 4; 4; 0; 0; 0; 0; 0), - оптимальный, F15)=-38.

Так как в последней симплексной таблице среди чисел i () нет отрицательных, то план Х5 является оптимальным, поскольку все искусственные переменные в нем х6 - х8 равны нулю.

Таким образом, Х*=(2; 4; 4; 0; 0), Fmin*)=-F1mах*)=38.

Ответ: оптимальным считается переработка руды в количестве 2, 4 и 4 тонн соответственно по 1-му, 2-му и 3-му процессам. При этом суммарные затраты будут минимальными и составят 38 тыс. грн.


3.6 Двойственность в линейном программировании и ее применение в экономическом анализе

3.6.1. Понятие двойственной задачи линейного программирования. Правила построения

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

Двойственная задача строится по отношению к прямой задаче, записанной в стандартной форме:

F=c1x1+c2x2+…+cnxn       max   (3.21)

Задача, состоящая в нахождении минимального значения функции:

L = b1y1 + b2y2 + … + bmym          (3.24)

при условиях:

называется двойственной по отношению к задаче (3.21) – (3.23).

Правила построения двойственной задачи приведены в таблице:


Структурные характеристики ЗЛП

Задача линейного программирования

Прямая

Двойственная

1.Целевая функция

Максимизация (max)

Минимизация (min)

2.Количество переменных

n переменных

Равно количеству ограничений прямой задачи (3.22),  yi,  т.е. m

3.Количество ограничений

m ограничений

Равно количеству переменных прямой задачи xj, , т.е n

4.Матрица коэффициентов в системе ограничений

5.Коэффициенты при переменных в целевой функции

c1,c2,…,cn      

b1,b2,…,bm

6.Правая часть системы ограничений

b1,b2,…,bm

c1,c2,…,cn      

7.Знаки в системе ограничений

а) xj ≥ 0- условие неотрицательности

j-е ограничение имеет знак «≥»

б) на переменную  xj  не наложено условие неотрицательности

j-е ограничение имеет знак «=»

в) i-е ограничение имеет знак «≤»

переменная  yi≥0

г)  i-е ограничение имеет знак «=»

на переменную  yi   не наложено условие неотрицательности

Примечание

  1.  Прямая задача на максимум и двойственная на минимум являются взаимодвойственными задачами. Поэтому можно считать задачу (3.24)–(3.26) прямой ЗЛП , а задачу (3.21) – (3.23) – двойственной к ней задачей. При этом правила построения двойственной ЗЛП сохраняются, лишь с тем изменением, что исходной считается задача на минимум.
  2.  Если исходная задача решается на  max  (min), а в системе ограничений i-е  (j-е) ограничение имеет знак «≤» («≥»), то для построения двойственной задачи необходимо:

а) либо домножить обе части  i-го (j-го) неравенства на (-1) и поменять знак на «≤» («≥»);

б) либо привести  i-е (j-е) ограничение к равенству путем введения дополнительной переменной xn+i≥0 с соответствующим знаком.

Пример 3.5

Задана прямая задача:

F = x1 - 2x2 + 5x3   max

2x1 + 2x2 + 4x3   ≤ 18

2x1 + x2      - 3x3  =20

5x1 + 3x2  + 6x3  ≥ 19

x1,x2 ≥0

Составить двойственную задачу.

Решение.

Прежде всего 3е ограничение умножим на (-1), так как оно имеет знак «≥» (Примечание 2а).Это ограничение принимает вид:

-5x1+3x2-6x3 ≤ -19.

Матрица коэффициентов при неизвестных в ограничениях будет иметь вид (Таблица: правило 4):

Запишем транспонированную к ней матрицу:

Тогда двойственная задача запишется:

Так как в прямой задаче второе ограничение имеет знак «=», то переменная y2 не имеет ограничения на знак (Таблица: правило 7г). Переменные x1,x2≥0, следовательно, первое и второе ограничения двойственной задачи (двойственная задача на минимум) будут иметь знак «» (Таблица: правило 7а). Третье ограничение двойственной задачи имеет знак «=» так как переменная x3  не имеет ограничения на знак (таблица: правило 7б).

3.6.2. Экономическая интерпретация двойственности

Рассмотрим примеры некоторых математических моделей ЗЛП, построенных в разделе 2, и составим для них двойственные задачи, пользуясь правилами таблицы (см. раздел 3.5.1).

Двойственная задача:

L = 6y1 + 8y2 + y3 + 2y4   min

y1 + 2y2 - y3 +0y4 ≥ 3

2y1 + y2 + y3 + y4 ≥ 2

yI ≥ 0,

Прямая задача:

 F = 3x1 + 2x2    max

x1    + 2x2 ≤ 6

2x1 + x2    ≤ 8

        x2    ≤ 2

x1,x2 ≥ 0

Пример 3.6 Задача об использовании сырья (пример 2.1)

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

Таким образом, yі ≥ 0, , можно считать оценкой единицы i-го ресурса, например его ценой или ценностью. Так y1 и y2 - оценки использования единицы продуктов А и В соответственно.

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

Наряду с выпуском продукции с целью получения максимальной прибыли от ее реализации (целевая функция прямой задачи) фирма решает задачу о реализации ресурсов на сторону. Условием такой реализации будет превышение суммарной стоимости использованных на производство единицы j-го вида красок (j=1,2) ресурсов (левая часть системы ограничений двойственной задачи) над прибылью, которую фирма получает от реализации единицы готовой продукции, т.е. красок Е и I (правая часть системы ограничений двойственной задачи).

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

Кроме того, из экономического содержания следует неотрицательность оценок yi, т.е., yi≥0, .

Пример 3.7 Задача об ассортименте продукции (пример 2.2)

Двойственная задача:

L = 430y1 + 460y2 + 420y3  min

y1    + 3y2 + y3       ≥ 3

2y1 + 0y2 + 4y3    ≥ 2

y1    + 2y2 + 0*y3 ≥ 5

yi ≥ 0,

Прямая задача:

F = 3x1 + 2x2 + 5x3    max

x1 + 2x2 + x3   ≤430

3x1       +2x3 ≤ 460

x1+4x2    ≤ 420

xj ≥ 0,

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

Исходя из данного определения двойственных переменных, целевая функция двойственной задачи выражает минимальную суммарную оценку сдачи предприятием, например, в аренду своего оборудования. Условием применения такой стратегии является превышение полных затрат на производство j-го вида готовой продукции (левая часть системы ограничений двойственной задачи) над ожидаемой прибылью от ёё реализации (правая часть системы ограничений двойственной задачи).

Из экономического смысла двойственных переменных следует, что yi≥0, .

Пример 3.8 Задача о раскрое и минимизации обрезков (пример 2.5)

Прямая задача:

F = 4x1 + 3x2 + x3 + 0*x4 + x5 + 2x6  min

     2x2 + 2x3 + 4x4 + x5           ≥ 150

x1+  x2      +2x5        ≥ 200

x1              +x3   2x6   ≥ 300

xj ≥ 0,

Двойственная задача:

L = 150y1 + 200y2 + 300y3  max

0*y1 + y2        + y3       ≤ 4

2y1    + y2        + 0*y3  ≤ 3

2y1    + 0*y2  + y3       ≤ 1

4y1    + 0*y2  + 0*y3 ≤ 0

y1       + 2y2     + 0*y3 ≤ 1

0*y1  + 0*y2 + 2y3    ≤ 2

yi ≥ 0,

В данном случае прямой является задача на минимум. Поэтому двойственная задача строится на максимум (раздел 3.5.1, примечание 1).

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

Таким образом, переменные yi () являются оценками i-го типа нестандартного рулона, например, могут характеризовать удельную экономию бумаги на 1 метр одного нестандартного рулона соответствующей длины.

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

Естественное условие yi ≥ 0 ().


Пример 3.9 Задача о рационе
(пример 2.3)

Двойственная задача:

L = 60y1 + 50y2 ® max

y1   + 2y2  ≤ 19

3y1 + 4y2 ≤ 24

4y1 + 2y2 ≤ 25

yi ≥ 0,

Прямая задача:

F = 19x1 + 24x2  + 25x3 ® min

x1    + 3x2 + 4x3  ≥ 60

2x1 + 4x2 + 2x3 ≥ 50

xj ≥0,

Двойственные переменные y1 и y2 выражают оценку питательного вещества A и В соответственно. Таким образом, целевая функция двойственной задачи характеризует суммарную оценку питательных веществ в кормовой смеси, а ограничения отражают рентабельность использования i-го вида корма: в левой части стоит внутренняя суммарная оценка питательных веществ А и В в 1 кг. корма каждого вида, а в правой – внешняя оценка 1 кг. корма i-го вида (цена за 1 кг.).

Итак, рассмотрев четыре пары двойственных задач, можно сделать вывод, что переменные двойственной задачи yi () в общем случае представляют собой ценность (оценку) i-го ограничения прямой задачи (иногда их называют теневыми ценами). Поэтому, придавая двойственным переменным конкретное экономическое содержание, необходимо исходить из постановки каждой конкретной задачи.

3.6.3. Связь между решениями прямой и двойственной задач

Каждая из задач двойственной пары (3.21)-(3.23) и (3.24)-(3.26) фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой. Однако, при определении симплексным методом оптимального плана одной из задач, тем самым находится решение и другой задачи.

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

Теорема 3.6

1. Если одна из пары двойственных задач (3.21)-(3.23) и (3.24)-(3.26) имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т.е. Fmax =Lmin.

2. Если же целевая функция одной из пары двойственных задач не ограничена (для исходной (3.21)-(3.23) – сверху, для двойственной (3.24)-(3.26) – снизу), то другая задача вообще не имеет планов.

Экономическое содержание теоремы (в терминах постановки задачи об использовании сырья):

1. Допустимый план производства и вектор оценок ресурсов оказываются оптимальными тогда, когда объем реализации продукции, измеренный во внешних ценах Сj  будет равен суммарной оценке всех ресурсов, измеренных во внутренних «ценах» уi, выделенных для производственного потребления.

2. Никакой допустимый план производства Х=(х1…хп) не будет оптимальным, если используемые ресурсы нельзя оценить во внутренних «ценах» уi. И наоборот, если внутренние оценки ресурсов уi чрезмерно завышены, то ни один план производства Х не будет рентабельным.

Теорема 3.7

Чтобы допустимые решения Х* и Y* пары двойственных задач (3.21)-(3.23) и (3.24)-(3.26) были оптимальными, необходимо и достаточно выполнения условий:

(a) для любого j (): (-Cj) = 0

(b) для любого i ():

Условие (а) эквивалентно системе:

x*j =0, > Cj   (a1)

x*j >0, = Cj   (a2)

Условие (b)эквивалентно системе:

 (b1)

 (b2)

Экономическое содержание теоремы

Если полные затраты на производство j–го вида продукции превосходят его цену, то данный вид продукции не войдёт в оптимальный план производства (а1), если же эти затраты совпадают, то выпуск j–го вида продукции оправдан по затраченным ресурсам и её производство целесообразно (а2).

Двойственные оценки оптимального плана – это мера дефицитности ресурсов. Ресурс, используемый в оптимальном  плане производства полностью, является дефицитным, его двойственная оценка положительна, дальнейшее его увеличение целесообразно (b2). Чем выше значение уi*, тем ресурс дефицитнее. Если ресурс расходуется не полностью, то он избыточен, его дальнейший рост на эффективность работы предприятия не влияет, двойственная оценка такого ресурса: уi*=0 (b1).

Теорема 3.8

Если основная задача ЛП имеет оптимальный план Х*, то Y*=Сб * Р-1 является оптимальным планом двойственной задачи, где Сб – вектор –строка, состоящая из коэффициентов при базисных переменных в целевой функции (3.14) задачи (3.14)-(3.15) в последней симплексной таблице, а Р-1 – матрица, обратная матрице Р, составленная из компонентов векторов последнего базиса в исходной системе ограничений (3.15).

Примечание

В случае, когда среди векторов Р1, Р2,…, Рn+m, составленных из коэффициентов при неизвестных в системе уравнений (3.15), имеется m единичных, указанную матрицу P-1 образуют числа первых m строк последней симплекс-таблицы, стоящие в столбцах данных векторов, а оптимальный план двойственной задачи Y* определяется по следующему правилу:

,  если ci = 0

,  если ci ≠ 0

для всех , гдеi – элемент (m+1)-ой строки столбцов единичных векторов первоначального базиса.

Пример 3.10

Рассмотрим задачу об использовании сырья (пример 2.1). Найдем оптимальный план соответствующей  двойственной задачи (пример 3.5). Решение прямой задачи приводится в разделе 3.4 (см пример 3.3).

Рассмотрим последнюю симплекс-таблицу:

i

Базис

Сб

Р0

3

2

0

0

0

0

Х1

Х2

Х3

Х4

Х5

Х6

1

Х2

2

4/3

0

1

2/3

-1/3

0

0

2

Х1

3

10/3

1

0

-1/3

2/3

0

0

3

Х5

0

3

0

0

-1

1

1

0

4

Х6

0

2/3

0

0

-2/3

1/3

0

1

5

38/3

0

0

1/3

4/3

0

0

у*5

у*6

у*1

у*2

у*3

у*4

Воспользуемся Теоремой 3.3 для нахождения Y*.

Матрицу Р образуют вектора Р2 , Р1, Р5, Р6, соответствующие базисным переменным последней симплекс-таблицы, взятые из исходной системы уравнений:

х1    + 2х2 + х3  =6

1 + х2        +х4   =8

1  + х2     5   =1

        х2        +х6  =2

то есть :  Р2      Р1      Р5       Р6

2       1         0        0

Р =   1       2         0        0

1       -1        1        0

1       0         0        1

Сб = (2;3;0;0).

Таким образом,

Очевидно, что данное оптимальное решение Y* легче получить, воспользовавшись приложением к Теореме 3.8.

Действительно, так как исходная задача имеет 4 единичных вектора Р , Р1, Р5, Р6, то обратная матрица Р-1 будет записана в первых 4-х строках последней симплекс-таблицы (в столбцах переменных Х3, Х4, Х5, Х6),  значения двойственных переменных – в тех же столбцах последней 5-й строки (поскольку Сi=0, i = 3,4,5,6).

Итак, анализируя оптимальное решение двойственной задачи, можно сделать следующие выводы:

1) 1й и 2ой ресурсы (продукты А и В) являются дефицитными, так как соответствующие им двойственные переменные у*1 =1/3 и у*2=4/3 положительны, причем, продукт В более дефицитный   (у*2  > у*1) ;

2) 3й и 4й ресурсы (ограничения на спрос) не дефицитны (у*3 = у*4=0). В частности, подобную информацию можно получить с помощью оптимальных дополнительных переменных прямой задачи, которые численно выражают разность между двумя частями соответствующих ограничений: Х3=Х4=0 – остаток у дефицитных ресурсов отсутствует, Х5=3, Х6=2/3 – величина дисбаланса между спросом на товар и объемом его производства;

3) кроме того, дополнительные двойственные переменные у*5 = у*6 = 0 характеризует рентабельность выпускаемой продукции соответственно Е и I. Они показывают, на сколько внутренняя оценка производства j-го вида продукции превосходит его внешнюю оценку (дополнительная двойственная переменная положительная) или, что производство данной продукции оправданно по отношению к затраченным ресурсам (дополнительная двойственная переменная равна нулю);

4) суммарная оценка использованных в производстве ресурсов Lmin совпадает с полученным от реализации продукции доходом Fmax, т.е. Lmin=Fmax=38/3 тыс. грн.

Пример 3.11

Рассмотрим двойственную задачу для задачи о рационе (см. примеры 2.3 и 3.9):

L = 60y1 + 50y2 max

y1    + 2y2≤ 19

3y1 + 4y2 ≤ 24

4y1 + 2y2 ≤ 25

yj ≥ 0, j=1,2

Найдем оптимальное решение пары двойственных задач, решив двойственную задачу симплекс – методом (она соответствует виду ЗЛП, для которой описан алгоритм симплексного метода).

Каноническая форма:

L = 60y1 + 50y2  max

y1   + 2y2 + у3 =19

3y1 + 4y2          4 =24

4y1 + 2y2      5    =25

yj ≥ 0;

Решение оформим в виде последовательности симплекс-таблиц.

i

Базис

Сб

Р0

60

50

0

0

0

Y1

Y2

Y3

Y4

Y5

1

Y3

0

19

1

2

1

0

0

2

Y4

0

24

3

4

0

1

0

3

Y5

0

25

4

2

0

0

1

4

0

-60

-50

0

0

0

1

Y3

0

51/4

0

3/2

1

0

-1/4

2

Y4

0

21/4

0

5/2

0

1

-3/4

3

Y1

60

25/4

1

½

0

0

¼

4

375

0

-20

0

0

15

1

Y3

0

48/5

0

0

1

-3/5

1/5

2

Y4

50

21/10

0

1

0

2/5

-3/10

3

Y1

60

26/5

1

0

0

-1/5

2/5

4

417

0

0

0

8

9

х*4           

х*5         

х*1           

х*2          

х*3

Так как все yj ≥ 0; , то план оптимален:

Y* = (26/5; 0; 0; 21/10; 45/5; 0; 0) , Lmax = 417.

Согласно приложению к теореме 3.3. имеем: Х*=(0;8;9;0;0); Fmin=Lmax=417.

Таким образом, рекомендуется составить кормовую смесь из 8 и 9 кг кормов 2-го и 3-го видов (х*2 = 8, х*3 = 9) соответственно Их использование оправдано (у*4 = у*5 = 0). Первый вид корма использовать не целесообразно (х*1=0). Возможный убыток при включении 1 кг корма 1-го вида в кормовую смесь составит 48/5 грн. (у*3 = 48/5).

Составленная кормовая смесь обеспечит животным получение необходимого количества питательных веществ А и В, а именно 50 и 60 единиц соответственно. Причем, питательное вещество А ценнее, чем вещество В (у*1=25/6 > у*2 = 21/10). При этом стоимость кормовой смеси будет минимальной и составит 417 грн.

3.6.4. Элементы экономико-математического анализа с использованием оптимальных двойственных оценок

  1.  Основные двойственные переменные показывают, на сколько изменится целевая функция прямой задачи при изменении соответствующего ресурса на единицу. Как следует из теоремы 3.6 (Fmax =Lmin), двойственная переменная численно равна вкладу в целевую функцию изменения соответствующего ограниченного ресурса на единицу.

Пусть, например, iй ресурс увеличили на единицу, т.е. b/i=bi +1. Тогда оптимальное значение целевой функции двойственной задачи также изменится:

.

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

  1.  Дополнительные двойственные переменные свидетельствуют о том, на сколько внутренние оценки ресурсов (левая часть ограничений), необходимых для производства -го вида продукции, превосходят его внешнюю оценку, т.е. цену продукции . Для продукции (или технологии), которая вошла в оптимальный план, их дополнительные двойственные переменные равны нулю. Их внедрение в производство не несет убытка. Если же некоторая продукция не вошла в оптимальный план, то изготовление такой продукции даст убыток. Возможный убыток равен значению дополнительной  двойственной переменной.
  2.  Состав двойственной переменной. Пусть, например, первый ресурс дефицитный. Ему соответствует дополнительная переменная прямой задачи Xn+1. Данной переменной соответствует столбец Рn+1. в оптимальной симплекс-таблице: . Если теперь первый ресурс изменить на единицу, а  - вектор значений оптимальных базисных переменных, то базисные переменные в оптимальном плане изменятся по формулам: . Пусть, например, в задаче об использования сырья (пример 2.1) первый ресурс (продукт А) увеличили на 1 тонну. Соответствующая данному ресурсу дополнительная переменная прямой задачи (х*3) представлена в оптимальной симплекс-таблице (см. пример 3.10) столбцом . Поэтому новые значения базисных переменных оптимального плана задачи изменятся по формулам:

При этом изменяется и значение целевой функции задачи:

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

  1.  Взаимозаменяемость ресурсов. Возникает естественный вопрос: если первый и второй ресурсы дефицитны и, например, первый уменьшился на единицу, то на сколько единиц нужно увеличить второй ресурс, чтобы экстремальное значение целевой функции не изменилось? Введем понятие коэффициента взаимозаменяемости .

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

Для задачи об использовании сырья значения коэффициентов взаимозаменяемости представлены в таблице:

1

2

3

4

1

1

4

0

0

2

1/4

1

0

0

3

1

0

4

0

1

Например, для рассчитаем коэффициент взаимозаменяемости второго ресурса первым: , т.е. при уменьшении суточного запаса продукта А на 1 тонну необходимо дополнительно увеличить суточный запас продукта В на 1/3 тонны чтобы значение целевой функции не изменилось. Как показывают расчеты значений коэффициентов взаимозаменяемости для рассматриваемого примера его значение больше 1, если более дефицитный ресурс заменяется менее дефицитным, и меньше 1, если происходит обратная замена. Знак «» означает, что заменить уменьшение дефицитного ресурса недефицитным не возможно, а «0» означает, что при уменьшении недефицитного ресурса не требуется дополнительное увеличение дефицитного ресурса.

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

Пусть в рассматриваемом примере фирма разработала новый вид продукции – краску для наружных работ К. Апробация его позволила определить расход каждого ограниченного ресурса на 1 тонну краски: по ¾ тонны продуктов А и В, а проведенные маркетинговые исследования показали, что цена за 1 тонну данной краски должна составлять 1,5 тыс. грн. Требуется выяснить целесообразность внедрения в серийное производства краски К, т.е. обеспечит ли ее выпуск увеличение целевой функции (дохода от реализации). Обозначим через  планируемый объем производства краски К. Как отмечалось выше, каждой основной переменной прямой задачи соответствует ограничение двойственной. Если  то соответствующее ему ограничение выполняется как строгое равенство (теорема 3.2):

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

Таким образом, показателем рентабельности (оправданности по затратам) нового вида продукции является величина: , где  - суммарные затраты на производство единицы продукции j-го вида, измеренные во внутренних ценах (двойственных оценках),  - внешняя оценка единицы продукции j-го вида (например, ее цена). Если , внедрение в производство продукции j-го вида оправдано по затратам дефицитных ресурсов, если , производство не выгодно. Причем равенство нулю () позволяет определить минимальное (граничное) значение внешней оценки продукции j-го вида, при которой ее производство будет рентабельно.

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

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


4. специальные задачи Линейного программирования: сети

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

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

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

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

Рассмотрим более подробно типичные примеры специальных ЗЛП и методы их решения, а именно: транспортную задачу и модификации ее постановки на сетевых моделях (графах).


4.1 Транспортная задача

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

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

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

4.1.1. Постановка транспортной задачи

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

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

    (4.1)

Обозначим через  - количество груза перевозимого из i-го пункта производства в j-й пункт потребления, и через  - стоимость транспортировки одного изделия (единицы груза) из пункта производства i в пункт потребления j.

Задача состоит в том, чтобы найти план перевозок , минимизирующий суммарные затраты на перевозки:

    (4.2)

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

     (4.3)

0; i=1,2,…, m,  j=1,2,…,n   (4.4)

Условия (4.3) и (4.4) образуют систему ограничений: первая группа ограничений (4.3) указывает, что суммарный объем перевозок из некоторого исходного пункта равен произведенному количеству этой продукции; вторая группа ограничений (4.3) требует, чтобы суммарные перевозки продукции в некоторый пункт потребления полностью удовлетворили спрос на эту продукцию. Условия баланса (4.1) означают, что суммарный объем производства равен суммарному спросу.

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

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

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

В случае, если , тогда вводится фиктивный (n+1)-й пункт назначения с потребностью  и соответствующие тарифы считаются равными нулю: сin+1 = 0  ().

Если , вводится фиктивный (m+1)-й пункт отправления с запасом груза , а cm+1, j = 0,

С помощью этих преобразований открытая транспортная задача сводится к закрытой.

Любой план перевозок , удовлетворяющий системе ограничений (4.3) и (4.4), называется допустимым.

Опорный невырожденный план транспортной задачи должен иметь ровно n+m-1 отличных от нуля неизвестных.

Итак, транспортную задачу можно сформулировать следующим образом.

Дана система ограничений (4.3), (4.4) и целевая функция (4.2). Требуется среди множества решений системы (4.3) найти такой неотрицательный план перевозок, который минимизирует целевую функцию.


4.1.2. Методы решения транспортной задачи

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

Шаг 1. Найти начальное допустимое решение.

Шаг 2. Выделить из числа небазисных переменных вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности , закончить вычисления; в противном случае перейти к шагу 3.

Шаг 3. Выбрать выводимую из базиса переменную (используя условие допустимости) из числа переменных текущего базиса; затем найти новое базисное решение. Вернуться к шагу 2.

Рассмотрим работу данного алгоритма на примере.

Пример 4.1

Для строительства четырех дорог используется гравий из трех карьеров. Запасы гравия в каждом из карьеров соответственно равны 120, 280 и 160 тонн потребности в гравии для строительства каждой из дорог соответственно равны 130, 220, 60 и 70 тонн известны также тарифы перевозок 1 тонны гравия из каждого карьера к каждой из строящихся дорог, которые задаются матрицей:

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

Построим математическую модель данной задачи. Пусть xij – количество тонн гравия, перевозимое из i-го карьера на строительство j-й дороги,

Целевая функция задачи выражает минимальные издержки по транспортировке гравия на строительство трех дорог и имеет вид:

F=1x11+7x12+9x13+5x14+4x21+2x22+6x23+8x24+3x31+8x32+1x33+2x34→min

Балансные ограничения на:

  •  вывоз гравия из карьеров:

1-го:  x11 + x12 + x13 +x14 = 120;

2-го:  x21 + x22 + x23 + x24 = 280;

3-го:  x31 + x32 + x33 + x34 = 160;

  •  удовлетворение потребности в гравии на строительстве дорог:

1-й:  x11 + x21 + x31 = 130;

2-й:  x12 + x22 + x32 = 220;

3-й:  x13 + x23 + x33 = 60;

4-й:   x14 + x24 + x34 = 70;

Естественное ограничение: xij ≥ 0,

Решение 

Исходные данные задачи сведем в таблицу (табл. 4.1).

Таблица 4.1

Пункты отправления

Пункты назначения

Запасы

В1

В2

В3

В4

А1

А2

А3

1

4

3

7

2

8

9

6

1

5

8

2

120

280

160

Потребности

130

220

60

70

Как видно из таблицы 4.1, запасы гравия в карьерах (120+280+160=560) больше, чем потребности в нем (130+220+60+70=480) на строящихся дорогах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный пункт назначения В5 с потребностями, равными 560-480=80 тонн. Тарифы перевозки 1 тонны гравия из всех карьеров в пункт В5 полагаем равным нулю. В результате получаем закрытую модель транспортной задачи (см. таблицу 4.2).

Шаг 1 Найдем начальное допустимое решение методом минимального элемента (метод наименьшей стоимости).

Данный метод заключается в следующем. На каждой итерации заполняется одна из допустимых ячеек транспортной таблицы, пока не будет заполнено n+m-1 ячейка. Выбор ячейки AiBj осуществляется по наименьшему тарифу. Каждая выбранная для заполнения ячейка характеризуется двумя числами ai и bj, записанными в строке и столбце, на пересечении которых стоит данная ячейка. Из этих чисел выбирается . При этом исчерпывается либо строка (ai' = 0), либо столбец (bj' = 0), либо одновременно и строка, и столбец (ai'  = bj' = 0). Таким образом, после заполнения ячейки AiBj необходимо пересчитать остатки в данных строке и столбце по следующему правилу:

ai'  = 0, bj' = bj - ai,  если ai < bj,  (а)

bj' = 0, ai'  = ai - bj,   если ai > bj,  (в)

ai'  = bj' = 0,    если ai = bj.  (с)

Затем выбирают новую допустимую ячейку для заполнения по наименьшему из оставшихся тарифов. Причем в случае (а) исчерпывается i-я строка, а в случае (в) – j-й столбец таблицы. Ячейки из этой строки (столбца) становятся недопустимыми для заполнения и из дальнейшего рассмотрения исключаются. Заполнение таблицы прекращается после того, как записаны в ячейки n+m-1 положительные переменные.

Замечание

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

Для нашего примера построение начального опорного плана методом минимального элемента проиллюстрировано в таблице 4.2.

Таблица 4.2

Пункты отправления

Пункты назначения

Запасы

В1

В2

В3

В4

В5

А1

1

7

9

5

0

40

80

120

40

0

А2

4

2

6

8

0

60

220

280

60

0

А3

3

8

1

2

0

30

60

70

160

100

0

Потребности

130

90

60

0

220

0

60

0

70

0

80

0

560

Выбираем ячейку с наименьшим тарифом. Это может быть одна из трех ячеек с тарифом 0: А1В5, А2В5, А3В5; например ячейку А1В5. Тогда: .

Пересчитываем остатки по формуле (в): b5' = 0, a1'  = 120 – 80 = 40.

Столбец В5 исчерпывается, и все ячейки этого столбца из рассмотрения исключаются.

Выбираем следующую допустимую ячейку с наименьшим тарифом 1: А1В1 или А3В3, например А1В1: .

Пересчитываем остатки по формуле (а): a1'  = 0, b1' = 130 – 40 = 90. Оставшиеся ячейки первой строки из рассмотрения исключаются.

Для ячейки А3В3: . Пересчет: a3'  = 0, b3'=160–60=100 (формула (в)). Процесс дальнейшего построения опорного плана представлен в таблице 4.2.

Таким образом, имеем начальный опорный план:

Для данного плана перевозок  транспортные расходы составят:

F(X0) = 40*1 + 80*0 + 60*4 + 220*2 + 30*3 + 60*1 + 70*2 = 1010 у.д.е.

Шаг 2 Проверяем построенное начальное допустимое решение Х0 на оптимальность методом потенциалов.

Алгоритм метода потенциалов

  1.  Построить систему потенциалов  - действительные целые числа, сопоставляемые строке i и столбцу j соответственно.  Для каждой базисной переменной текущего решения потенциалы ui и vj должны удовлетворять уравнению:

   (4.5)

Так как базисных переменных m+n-1, то мы получим систему из m+n-1 уравнений вида (4.5) относительно m+n неизвестных. Значения потенциалов можно найти из этой системы, придав одному из них произвольное значение (обычно ui полагается равным нулю), и затем, решая систему относительно m+n-1, остальных потенциалов.

  1.  Определить оценки оптимальности для небазисных переменных:

,   (4.6)

где crk – транспортные расходы по перевозке груза из пункта Аr в пункт Вk.

Рассчитанные значения rk заносятся в нижний левый угол ячеек транспортной таблицы.

  1.  Проверить план на оптимальность:

а) если все rk0, то план оптимальный, конец вычислений;

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

  1.  Переход к лучшему опорному плану:

а) Определить переменную, вводимую в базис:

,    (4.7)

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

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

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

Из базиса выводится переменная, помеченная и имеющая наименьшее значение Xmin.

в) Вычислить новые значения базисных переменных:

  •  для переменных, не вошедших в цикл, их значения не меняются;
  •  значение переменной, вошедшей в цикл, увеличивается на величину Xmin, если она помечена , и уменьшается на величину Xmin, если .
  1.  Переход к шагу 2.

Построим систему потенциалов для допустимого решения Х0 из нашего примера (см. табл. 4.3)

Таблица 4.3

       vj

ui

v1=1

v2= -1

v3= -1

v4=0

v5=0

u1=0

1

7

9

5

0

40

-8

-10

-5

80

u2=3

4

2

6

8

0

60

220

-4

-5

3

  

u3=2

3

8

1

2

0

30

-7

60

70

2

Уравнения (4.5) для базисных переменных будут иметь вид:

x11: u1 + v1 = 1  x22: u2 + v2 = 2  x34: u3 + v4 = 2

x15: u1 + v5 = 0  x31: u3 + v1 = 3

x21: u2 + v1 = 4  x33: u3 + v3 = 1

Полагая u1=0, находим  v1=1, v5=0, u2=3, v2=-1, u3=2, v3=-1, v4=0.

Оценки для небазисных переменных рассчитываем по формуле (4.6):

x12:  12=u1+v2–с12=0+(-1)–7=-8,  x24:  24=u2+v4–с24=3+0–8=-5,

x13:  13=u1+v3–с13=0+(-1)–9=-10,  x25:  25=u2+v5–с25=3+0–0=3,

x14:  14=u1+v4–с14=0+0–5=-5,  x32