«Мастяева И.Н. Семенихина О.Н. Методы оптимизации Москва 2003 УДК 519.8 БМК 22.18 М – 327 И.Н. Мастяева, О.Н. Семенихина. МЕТОДЫ ОПТИМИЗАЦИИ: / Московский государственный университет экономики, статистики и информатики. ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Московский государственный университет экономики,

статистики и информатики

Мастяева И.Н.

Семенихина О.Н.

Методы оптимизации

Москва 2003

УДК 519.8

БМК 22.18

М – 327

И.Н. Мастяева, О.Н. Семенихина. МЕТОДЫ ОПТИМИЗАЦИИ: /

Московский государственный университет экономики, статистики и

информатики. – М.: МЭСИ, 2003. – 135 с.

© Ирина Николаевна Мастяева, Ольга Николаевна Семенихина 2003 © Московский государственный университет экономики, статистики и информатики, 2003 2

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

1.1 ЛИНЕЙНЫЕ МОДЕЛИ В ЭКОНОМИКЕ. ПОСТАНОВКИ ЗЛП........ 1.2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗЛП

1.3. РЕШЕНИЕ ЛИНЕЙНЫХ МОДЕЛЕЙ СИМПЛЕКС-МЕТОДОМ.... 1.4. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД (Р-МЕТОД)

1.5. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ... 1.6. РЕШЕНИЕ ЗЛП ДВУХЭТАПНЫМ СИМПЛЕКС-МЕТОДОМ........

2. СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ..

2.1. ЗАДАЧА ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

2.2. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

3. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

3.1. ЗАДАЧА РАСПРЕДЕЛЕНИЯ КАПИТАЛОВЛОЖЕНИЙ................. 3.2. ЗАДАЧА УПРАВЛЕНИЯ ЗАПАСАМИ

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

4.1 Методы одномерной оптимизации

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

4.1.2. Поиск отрезка, содержащего точку максимума. Алгоритм Свенна

4.1.3. Метод золотого сечения

4.2. Методы безусловной оптимизации.

4.2.1. Постановка задачи.

4.2.2. Метод скорейшего спуска – метод Коши метод первого порядка

4.3. МЕТОДЫ УСЛОВНОЙ ОПТИМИЗАЦИИ

4.3.1. Постановка задачи. Классификация методов

4.3.2. Метод Зойтендейка

Введение Методы оптимизации применяются в различных отраслях человеческой деятельности. Процесс принятия решения в любой области распадается на несколько этапов:

постановка задачи;

построение модели;

решение моделей с помощью выбранного метода оптимизации;

реализация полученного результата.

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

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

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

1.1. Линейные модели в экономике. постановки ЗЛП Пример 1.1. Фабрика выпускает продукцию двух видов: П1 и П2.

Продукция обоих видов поступает в оптовую продажу. Для производства этой продукции используются три исходных продукта – A, B, C.

Максимально возможные суточные запасы этих продуктов составляют 6, и 5 т соответственно. Расходы сырья A, B, C на 1 тыс. изделий П1 и П приведены в табл. 1.

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

шт. в сутки.

Оптовые цены 1 тыс. шт. изделий П1 равны 3 тыс. руб., 1 тыс. шт. П – 2 тыс. шт.

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

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

В рассматриваемом примере имеем следующее:

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

X1 – суточный объём производства изделия П1 в тыс. шт.;

X2 – суточный объём производства изделия П2 в тыс. шт.

Целевая функция. Так как стоимость 1 тыс. изделий П1 равна 3 тыс.

руб., суточный доход от её продажи составит 3X1 тыс. руб. Аналогично доход от реализации X2 тыс. шт. П2 составит 2X2 тыс. руб. в сутки. При допущении независимости объёмов сбыта каждого из изделий общий доход равен сумме двух слагаемых – дохода от продажи изделий П1 и дохода от продажи изделий П2.

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

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

Расход исходного продукта Максимально возможный Это приводит к трём ограничениям:

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

X2 - X1 1 (соотношение величин спроса на изделия П1 и П2), X2 2 (максимальная величина спроса на изделия П2).

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

ограничения на их знак:

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

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

Определить суточные объёмы производства (Х1 и Х2) изделий П1 и П2 в тыс. шт., при которых достигается при Пример 1.2. (задача составления кормовой смеси или задача о диете).

Бройлерное хозяйство птицеводческой фермы насчитывает цыплят, которые выращиваются до 8-недельного возраста и после соответствующей обработки поступают в продажу. Недельный расход корма в среднем (за 8 недель) составляет 500г = 0.5 кг.

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

В табл. 2 приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из ингредиентов и удельную стоимость каждого ингредиента. Смесь должна содержать:

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

Математическая формулировка задачи.

Введём следующие обозначения:

Х1 – содержание известняка в смеси (кг);

Х2 – содержание зерна в смеси (кг);

Х3 – содержание соевых бобов в смеси (кг);

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

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

0.38Х1 + 0.001Х2 + 0.002Х3 0.008 х 10 000, Окончательный вид математической формулировки задачи:

при ограничениях 0.38Х1 + 0.001Х2 + 0.002Х Пример 1.3. (задача о раскрое или минимизации отходов (обрезков)).

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

Рассмотрим все возможные варианты раскроя стандартного рулона, соответствующие данные приведем в табл.4.

Определим переменные: Xj – количество стандартных рулонов, разрезаемых по варианту j, j =1, 2, Е, 6.

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

2X2 + 2 X3 + 4 X4 + X5 =150 – количество рулонов шириной 0,5 м, Выражение для суммарной величины потерь бумаги (отходы) (в м) имеет вид Таким образом, математическая модель в общем виде имеет вид при ограничениях:

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

ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Общая задача линейного программирования (ОЗЛП) может быть сформулирована следующим образом: найти значения переменных Х1, Х2, Е, Хn, максимизирующие линейную форму при условиях Соотношения (1.5) и (1.6) будем называть соответсвенно функциональными и прямыми ограничениями задачи линейного программирования (ЗЛП).

Значения переменных Хj (j = 1, 2,..., n) можно рассматривать как компоненты некоторого вектора X = ( X 1,, X 2,..., X n ) пространства Еn.

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

Множество всех планов задачи линейного программирования (1.4)будем обозначать Р.

Определение. План X = (X 1, X 2,...,X n ) будем называть решением задачи линейного программирования или ее оптимальным планом, если Определение. Будем говорить, что задача линейного программирования разрешима, если она имеет хотя бы один оптимальный план.

ОСНОВНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Такую ЗЛП можно поставить следующим образом: найти значения переменных X 1,, X 2,..., X n, максимизирующие линейную форму или в векторно-матричной форме где коэффициентов ограничений (1.8).

Задача (1.7)-(1.9) или (1.10)-(1.12) называется основной ЗЛП.

Основная ЗЛП является частным случаем общей ЗЛП при m1 = m, p = n.

КАНОНИЧЕСКАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Для построения общего метода решения ЗЛП разные формы ЗЛП должны быть приведены к некоторой стандартной форме, называемой канонической задачей линейного программирования (КЗЛП).

В канонической форме 1) все функциональные ограничения записываются в виде равенств с неотрицательной правой частью;

2) все переменные неотрицательны;

3) целевая функция подлежит максимизации.

Таким образом, КЗЛП имеет вид или в векторно-матричной форме КЗЛП является частным случаем общей ЗЛП при m1 = 0,p = n.

Очевидно, что определения плана и оптимального плана, данные для общей ЗЛП, справедливы и для КЗЛП.

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

а) максимизация целевой функции f (x ) = C1X1 + C2X2 +... + CnXn равносильна минимизации целевой функции - f (x ) = - C1X1 - C2X2 -... - CnXn;

б) ограничение в виде неравенства, например 3Х1 + 2Х2 - Х3 6, может быть приведено к стандартной форме 3Х1 + 2Х2 - Х3 + Х4 = 6, где новая переменная Х4 неотрицательна. Ограничение Х1 - Х2 + 3Х3 10 может быть приведено к стандартной форме Х1 - Х2 + 3Х3 - Х5 = 10, где новая переменная Х5 неотрицательна;

в) если некоторая переменная ХК может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду Графическим методом целесообразно решать ЗЛП, содержащие не более двух переменных.

Алгоритм графического метода рассмотрим применительно к задаче:

Шаг 1. Строим область допустимых решений (1.20) – область Р, т.е.

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

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

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

Полученная таким образом область допустимых решений Р – планов ЗЛП (рис. 1) есть многоугольник ABCDEF – замкнутое, ограниченное, выпуклое множество с шестью крайними или угловыми точками: A, B, C, D, E, F.

Шаг 2. Строим вектор-градиент f (x ), C = ( 3,2), указывающий направление возрастания функции f.

Шаг 3. Строим прямую С1Х1 + С2Х2 = const – линию уровня функции f (x ), перпендикулярную вектору-градиенту C : 3Х1 + 2Х2 = const (рис.

Шаг 4. В случае максимизации 3Х1 + 2Х2 = const в направлении вектора C до тех пор, пока она не покинет область Р. Крайняя точка (или точки) области, в которой линия уровня покидает допустимую область, и является решением задачи (рис.

3).

Крайняя точка С – точка максимума f (x ), С = X лежит на пересечении прямых (а) и (б). Для определения ее координат решим систему уравнений:

Подставляя значения Х*1 и X*2 в функцию f (x ), найдем Замечания.

1. В случае минимизации перемещать в направлении (- C ), противоположном C.

2. Если допустимая область решений Р представляет собой неограниченную область и прямая при движении в направлении вектора C (или противоположном ему) не покидает Р, то в этом случае f (x ) не ограничена сверху (или снизу), т.е.

Пример 1.4 Графическим способом решить ЗЛП Шаг 1. Строим область Р (pис. 4). Она является неограниченной.

Шаг 2. Строим вектор C = (2, 1).

Шаг 3. Строим линию уровня функции Шаг 4. Передвигая линию уровня в направлении вектора C = (2, 1), убеждаемся в неограниченном возрастании функции f (x ), т.e.

Пример 1.5 Решить графическим методом ЗЛП. Найти при ограничениях Из рис. 5 видно, что область допустимых решений пуста (Р= ).

Задача не имеет решения.

1. Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей: Х и Y. Завод располагает фондом рабочего времени в 4000 чел.-ч. в неделю. Для производства одной детали типа Х требуется 1 чел.-ч, а для производства одной детали типа Y – 2 чел.ч. Производственные мощности завода позволяют выпускать максимум 2250 деталей типа Х и 1750 деталей типа Y в неделю. Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю. Кроме того, еженедельно завод поставляет 600 деталей типа Х своему постоянному заказчику. Существует также профсоюзное соглашение, в соответствии с которым общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.

Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30 ф. ст., а от производства одной детали типа Y – 40 ф. ст.?

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

а) "Юпитер" – объем памяти 512 Кбайт, одинарный дисковод;

б) "Венера" – объем памяти 512 Кбайт, двойной дисковод;

в) "Марс" – объем памяти 640 Кбайт, двойной дисковод;

г) "Сатурн" – объем памяти 640 Кбайт, жесткий диск.

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

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

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

капитала таким образом, чтобы получать максимальные годовые проценты с дохода. Его выбор ограничен четырьмя возможными объектами инвестиций: А, В, С и D. Объект А позволяет получать 6% годовых, объект В – 8% годовых, объект С – 10%, а объект D – 9% годовых. Для всех четырех объектов степень риска и условия размещения капитала различны.

Чтобы не подвергать риску имеющийся капитал, менеджер принял решение, что не менее половины инвестиций необходимо вложить в объекты А и В. Чтобы обеспечить ликвидность, не менее 25% общей суммы капитала нужно поместить в объект D. Учитывая возможные изменения в политике правительства, предусматривается, что в объект С следует вкладывать не более 20% инвестиций, тогда как особенности налоговой политики требуют, чтобы в объект А было вложено не менее 30% капитала. Сформулировать для изложенной проблемы распределения инвестиций модель линейного программирования и решить графически, если в объект А нужно вложить ровно 30%, а в объект С ровно 20% общей суммы капитала.

4. "Princetown Paints Ltd" выпускает три основных типа румян – жидкие, перламутровые и матовые — с использованием одинаковых смесеобразующих машин и видов работ. Главному бухгалтеру фирмы было поручено разработать для компании план производства на неделю.

Информация о ценах продаж и стоимости 100 л товара приведена в таблице (ф. ст.).

Стоимость 1 чел.-ч составляет 3 ф. ст., а стоимость 1 ч приготовления смеси – 4 ф. ст. Фонд рабочего времени ограничен чел.-ч. в неделю, а ограничение на фонд работы смесеобразующих машин равно 5900 ч в неделю.

Издержки производства смеси Другие издержки В соответствии с контрактными соглашениями компания должна производить 25000 л матовых румян в неделю. Максимальный спрос на жидкие румяна равен 35000 л в неделю, а на перламутровые румяна – 29000 л в неделю.

Требуется:

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

5. Администрация компании "Nemesis Company", осуществляя рационализаторскую программу корпорации, приняла решение о слиянии двух своих заводов в Аббатс-филде и Берчвуде. Предусматривается закрытие завода в Аббатсфилде и за счет этого – расширение производственных мощностей предприятия в Берчвуде. На настоящий момент распределение рабочих высокой и низкой квалификации, занятых на обоих заводах, является следующим:

В то же время после слияния завод в Берчвуде должен насчитывать 240 рабочих высокой и 320 рабочих низкой квалификации.

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

1. Все рабочие, которые попали под сокращение штатов, получат выходные пособия следующих размеров:

Неквалифицированные рабочие – 1500 ф. ст.

2. Рабочие завода в Аббатсфилде, которые должны будут переехать, получат пособие по переезду в размере 2000 ф. ст.

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

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

6. Компания "Bermuda Paint" – частная промышленная фирма, специализирующаяся на производстве технических лаков. Представленная ниже таблица содержит информацию о ценах продажи и соответствующих издержках производства единицы полировочного и матового лаков.

Для производства 1 галлона матового лака необходимо затратить 6 мин трудозатрат, а для производства одного галлона полировочного лака – 12 мин. Резерв фонда рабочего времени составляет 400 чел.-ч. в день.

Размер ежедневного запаса необходимой химической смеси равен унциям, тогда как ее расход на один галлон матового и полировочного лаков составляет 0,05 и 0,02 унции соответственно. Технологические возможности завода позволяют выпускать не более 3000 галлонов лака в день.

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

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

б) Используя графический метод, определить ежедневный оптимальный план производства и соответствующую ему величину 7. На мебельной фабрике из стандартных листов фанеры необходимо вырезать заготовки трех видов в количествах, соответственно равных 24, 31 и 18 шт. Каждый лист фанеры может быть разрезан на загоTОBKИ Двумя способами. Количество получаемых заготовок при данном способе раскроя приведено в таблице. В ней же указана величина отходов, которые получаются при данном способе раскроя одного листа фанеры.

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

8. В отделе технического контроля (ОТК) некоторой фирмы работают контролеры разрядов 1 и 2. Норма выработки ОТК за 8-часовой рабочий день составляет не менее 1800 изделий. Контролер разряда проверяет 25 изделий в час, причем не ошибается в 98% случаев.

Контролер разряда 2 проверяет 15 изделий в час; и его точность составляет 95%.

Заработная плата контролера разряда 1 равна 4 долл. в час, контролер разряда 2 получает 3 долл. в час. При каждой ошибке контролера фирма несет убыток в размере 2 долл. Фирма может использовать 8 контролеров разряда 1 и 10 контролеров разряда 2.

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

9. Металлургическому заводу требуется уголь с содержанием фосфора не более 0,3 % и с долей зольных примесей не более 3, 25%. Завод закупает 3 сорта угля А, В, С с известным содержанием примесей. В какой пропорции нужно смешивать исходные продукты А, В, С, чтобы смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену?

Содержание примесей и цена исходных продуктов приведены в 10. Решить задачу из примера 1.2.

1.3. Решение линейных моделей симплекс-методом Рассмотрим каноническую задачу линейного программирования (КЗЛП) Будем в дальнейшем считать, что ранг матрицы А системы уравнений Ax = b равен m, причем m < n.

Запишем КЗЛП в векторной форме:

где a j – j-й столбец матрицы А.

Определение. Опорным планом (ОП) задачи линейного программирования будем называть такой ее план, который является базисным решением системы линейных уравнений A x = b. Согласно определению и предположению о том, что r(A)=m (как всякому опорному плану задачи линейного программирования (как и всякому базисному решению системы линейных уравнений подматрица В порядка m матрицы А и определенный набор m базисных переменных системы линейных уравнений A x = b.

Определение. m компонент базисного решения системы линейных уравнений A x = b, являющихся значениями соответствующих ему базисных переменных, будем называть базисными компонентами этого решения. Отметим, что базисные компоненты опорного плана неотрицательны; остальные n-m его компонент равны нулю. Очевидно, что число опорных планов задачи линейного программирования конечно и не C n. Число строго положительных компонент опорного плана превышает не превышает m.

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

Число К-матриц конечно и не превышает Cm. Каждая К-матрица определяет ОП КЗЛП и наоборот.

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

Пусть требуется решить задачу (1.21). Так как по доказанному выше решением задачи (1.21) является неотрицательное базисное решение системы линейных уравнений A x = b, то метод решения задачи (1.21) должен содержать четыре момента:

1) обоснование способа перехода от одного опорного плана (Кматрицы) к другому;

2) указание признака оптимальности, позволяющего проверить, является ли данный опорный план оптимальным;

3) указание способа построения нового опорного плана, более близкого к оптимальному;

4) указание признака отсутствия конечного решения.

ПЕРЕХОД ОТ ОДНОЙ К-МАТРИЦЫ ЗЛП К ДРУГОЙ К-МАТРИЦЕ

Пусть известна К-матрица:

базисных (единичных) столбцов матрицы – вектор, компоненты которого есть базисные компоненты опорного плана, определяемого матрицей (n-m) компонент опорного плана, определяемого матрицей K, равны план, определяемый матрицей K. Например, пусть план, определяемый K, имеет вид X =(2,0,1,0,0,4).

Итак, пусть К-матрица (1.25) определяет опорный план Выберем в матрице единичной подматрице, т.е. k N i, i = 1, m и такой, что в этом столбце есть хотя бы один элемент больше нуля.

над матрицей K один шаг метода Жордана-Гаусса. В результате получим новую матрицу выбора направляющего элемента a lK, позволяющие получить новую КS +1) теоремы:

бы один строго положительный элемент ( k N помощью одного шага метода Жордана-Гаусса можно построить новую где C N ( S ) – вектор, компонентами которого являются коэффициенты линейной функции опорного плана, определяемого матрицей K, назовем j-й симплексS ) разностью матрицы K.

где К – номер столбца a K ( k N i( S ), i = 1, m ) есть хотя бы один строго положительный Неравенство (1.32) вытекает из выражения (1.31), так как K < 0, K, является оптимальным.

a K ( k N i( S ), i = 1, m ) нет ни одного строго положительного элемента.

Тогда ЗЛП (1.13-1.15) не имеет конечного решения.

АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Будем считать, что известна исходная К-матрица К(0) задачи линейного программирования, определяющая исходный опорный план В симплексном методе последовательно строят К-матрицы К(0), К(1),..., К(s) задачи линейного программирования, пока не выполнится критерий оптимальности или критерий, позволяющий убедиться в отсутствии конечного решения. Рассмотрим алгоритм S-й итерации симплексного метода. В начале S-й итерации имеем К-матрицу К(s-1) задачи линейного программирования, определяющую опорный план значение линейной формы Шаг 3. Если a ik 0, i = 1, m, то ЗЛП не имеет конечного решения, иначе находим номер l из условия направляющий элемент на S-й итерации метода есть элемент a lk.

Шаг 4. Вычисляем компоненты вектора N :

направляющим элементом l k. Присваиваем переменной S алгоритма значение S+1 и переходим к шагу 1.

Пример 1.6. Симплекс-методом решить ЗЛП:

Приводим систему линейных неравенств (1.34) к каноническому виду, вводя в каждое неравенство дополнительную переменную Si, где i = 1,4. Получим систему линейных уравнений:

Целевая функция будет иметь вид Расширенная матрица K = системы линейных уравнений (1.35)является исходной К-матрицей К(0) ЗЛП, которая определяет исходный опорный план:

Результаты последовательных итераций симплекс-алгоритма удобно оформить в виде симплексной таблицы.

На второй итерации S=2, все (2) 0 j = 1,6, следовательно, опорный план определяемый К-матрицей К(2), оптимальный, Оптимальное значение линейной формы равно:

Пример 1.7. Симплекс-методом решить ЗЛП:

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

Из симплекс-таблицы при S = 2 следует, что согласно шагу симплекс-алгоритма данная ЗЛП не имеет конечного решения, т.к.

отрицательная симплекс-разность ( ) соответствует столбцу a 3, все элементы которого неположительны.

Предприятие производит 3 вида продукции: А1, А2, А3, используя сырье двух видов: В1 и В2. Известны затраты сырья i-го вида на единицу изделия j-го вида аij, количества сырья каждого вида bi (i=1,2), а так же прибыль, полученная от единицы изделия j-го вида сj (j=1,2,3).

Сколько изделий каждого вида необходимо произвести, чтобы получить 1)максимум прибыли; 2) максимум товарной продукции?

Обозначения: в таблице приведена матрица затрат: А=(аij), справа от таблицы значение bi (i=1,2) и внизу – сj (j=1,2,3).

3) Решить задачу при дополнительных условиях: предприятие платит за хранение единицы сырья В1 и В2 соответственно 0,1 и 0,3 денежных единицы.

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

1. (100, 100, 300) 2. (200, 100, 50) 3. (100, 100, 200) 4. (200, 100, 250) 5. (100, 100, 200) 6. (200, 100, 100) 7. (100, 300, 100) 8. (100, 200, 500) 9. (100, 100, 200) 10. (200, 100, 600) 1.4. Двойственный симплекс-метод (Р-метод) Пример 1.8. Рассмотрим следующую ЗЛП:

Приведем рассматриваемую ЗЛП к каноническому виду или Рассмотрим расширенную матрицу системы линейных уравнений (1.40):

Матрица P (0 ) содержит единичную подматрицу порядка 3 и, следовательно, определяет базисное решение системы уравнений (47), причем C N =( 0,0,0). Так как элементы (n + 1 = 6)-го столбца матрицы системы не являются неотрицательными, то она не является К-матрицей ЗЛП. Вычислим неотрицательными, то базисное решение X N ( 0 ) = (-3; -6; 3) не являющееся допустимым решением ЗЛП, является “лучшим”, чем оптимальное решение.

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

ОПРЕДЕЛЕНИЕ Р-МАТРИЦЫ ЗЛП

Определение. Р-матрицей КЗЛП (1.13-1.15) будем называть расширенную матрицу системы линейных уравнений, равносильной системе (1.14), содержащую единичную подматрицу порядка m на месте n первых столбцов, все симплекс разности которой неотрицательны.

Очевидно, что всякая Р-матрица ЗЛП определяет некоторое базисное решение системы уравнений (1.14) (см.пример 1.8) Определение. Базисное решение системы линейных уравнений (1.14), определяемое Р-матрицей, называется псевдопланом ЗЛП.

УСЛОВИЯ ПЕРЕХОДА ОТ ОДНОЙ Р-МАТРИЦЫ ЗЛП К ДРУГОЙ

Пусть известна Р-матрица P ( S ) ЗЛП (1.13-1.15), определяющая псевдоплан Условия перехода от матрицы P содержание теоремы 11.

Теорема 1.5. Пусть b l < 0 и в l -й строке матрицы P ( S ) есть хотя бы один отрицательный элемент. Тогда с помощью одного шага метода Жордана-Гаусса можно построить новую Р-матрицу P ( S +1), выбрав направляющий элемент из условия Замечание 1. Если в матрице P (S ) нет b l < 0, определяемый ею псевдоплан является решением ЗЛП.

Теорема 1.6. Пусть b l < 0 и в l-й строке матрицы P (S ) нет ни одного отрицательного элемента. Тогда множество планов Р ЗЛП (1.13пусто.

Замечание 2. При переходе от матрицы P (S ) к матрице P ( S +1) целевая функция изменяется в соответствии с формулой откуда следует, что так как bl(S ) < 0 и a lK ) < 0. Из неравенства (1.43) следует, что при переходе возрастает.

АЛГОРИТМ Р-МЕТОДА

Будем считать, что известна исходная Р-матрица P ( 0 ) задачи линейного программирования, определяющая исходный псевдоплан В методе последовательного уточнения оценок последовательно строят Р-матрицы P(1), P(2),..., P(S),... задачи линейного программирования, пока не получат Р-матрицу задачи линейного программирования, определяющую ее оптимальный план.

Рассмотрим алгоритм S-й итерации метода последовательного уточнения оценок. В начале S-й итерации имеем Р-матрицу P ( S 1) задачи линейного программирования, определяющую псевдоплан Шаг 1. Найдем номер l из условия Шаг 2. Если b l то псевдоплан является оптимальным опорным планом, а есть оптимальное значение линейной формы f (x ), иначе переходим к шагу 3.

Шаг 3. Если то задача линейного программирования не имеет решения (множество планов Р пусто), иначе переходим к шагу 4.

Шаг 4. Вычисляем для столбцов a j Е,m) симплекс-разности j и находим номер К из условия Направляющий элемент на S-й итерации метода есть элемент a lK 1).

Шаг 5. Вычисляем компоненты вектора N (S ) :

Шаг 6. Производим один шаг метода Жордана-Гаусса с направляющим элементом a lK 1). Вычисляем Жордана-Гаусса. Присваиваем переменной алгоритма S значение S + 1 и переходим к шагу 1.

РЕШЕНИЕ ЗАДАЧ Р-МЕТОДОМ

Решим задачу из примера 1.8. Результаты решения приведены в симплекс-таблице.

(1.39). Итак, Пример 1.9. Решим ЗЛП:

Приведем рассматриваемую ЗЛП к каноническому виду Расширенная матрица системы линейных уравнений (1.45) не являются Р-матрицей рассматриваемой ЗЛП, так как Следовательно, к решению ЗЛП (1.44) не применим Р-метод.

Пример 1.10. Найти минимум функции при ограничениях:

Решение. Приведем задачу к каноническому виду Так как расширенная матрица системы линейных уравнений рассматриваемой задачи является Рматрицей ( 1 = 6 > 0; 2 = 3 > 0), то задачу можно решить Р-методом.

Решение задачи ведем в симплексной таблице.

Так как bl(1) = b1(1) = -4 < 0, а все a1(1) 0, то множество планов ЗЛП (1.46) является пустым множеством.

Предприятию необходимо выпустить по плану продукции А1 – единиц, А2 – 300, А3 – 450. Каждый вид изделия может производиться на двух машинах. Полезное затрачиваемое время каждой машины 5000 мин.

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

Учитывать возможность перевыполнения плана.

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

ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ

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

Задачей, двойственной к ЗЛП (1.47)-(1.49), называется следующая ЗЛП Из приведенного определения следует, что двойственная ЗЛП строится по следующим правилам:

1) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, т.е. число переменных двойственной задачи (y1,..., ym) равно числу ограничений прямой задачи.

2) Каждой переменной прямой задачи соответствует ограничение двойственной задачи, т.е. число ограничений двойственной задачи равно числу переменных прямой задачи.

3) Матрица функциональных ограничений двойственной задачи получается путем транспонирования матрицы функциональных ограничений прямой задачи.

C целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а вектор b правой части прямой задачи – вектором целевой функции двойственной задачи.

5) Если целевая функция прямой задачи максимизируется, то целевая функция двойственной задачи минимизируется, а ограничения имеют вид, и наоборот.

Пример 1.11. Пусть прямая задача записана в виде основной ЗЛП:

Приведем задачу (1.55) к канонической форме:

Тогда двойственная задача (ДЗ) будет иметь вид:

Пример 1.12. Прямая задача Ограничение y1 + 0 y2 0, т.е. y1 0 является более жестким, чем условие неограниченности у1 в знаке, поэтому двойственная задача может быть записана в следующем виде:

Пример 1.13. Прямая задача Отбрасывая избыточные ограничения, получаем:

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

Очевидно, что задача, двойственная к двойственной, совпадает с прямой.

ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

двойственной ЗЛП, тогда соответственно прямой и двойственной задач.

Теорема 3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойственная (прямая) ЗЛП имеет решение, причем Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

Теорема 4. Планы x, y соответственно прямой и двойственной ЗЛП являются оптимальными тогда и только тогда, когда Условия (1.60) называются условиями дополнительной нежесткости.

Замечание 1. Для основной ЗЛП и двойственной к ней ЗЛП условия нежесткости имеют вид:

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

ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ ДВОЙСТВЕННОЙ

ЗАДАЧИ НА ОСНОВАНИИ ТЕОРЕМЫ

Пример 1.15. Рассмотрим задачу из примера 1.8:

Ее решение x = (3 / 2; 0), minf ( x ) = 3. Найдем решение задачи, двойственной к (1.63) используя теорему 4. Запишем двойственную к (1.63) задачу:

Применяем соотношение (1.62).

Так как х1*= 3/2 > 0, то 3у1* + 4у2* + у3* = 2. Далее, так как 3х1* + х2* = 9/2 + + > 3, то у1* = 0, и так как х1* + 2х2* = 3/2 + 0 < 3, то у3* = 0.

вектор y = ( 0; 1/ 2; 0) является решением задачи (1.64) на основании утверждению теоремы 3.

Пример 1.16. Найти решение прямой и двойственной задачи.

Х1 – не ограничена в знаке У2 – не ограничена в знаке.

Двойственная задача содержит две переменные, т.е. ее можно решать графически (рис. 6) Как видно из рис. 6, область допустимых решений – планов двойственной ЗЛП – Q представляет собой отрезок АВ, лежащий на прямой Y1 + 2Y2 = 5, так как первое ограничение задается в виде равенства.

Передвигая линию уровня функции 10Y1 + 8Y2 = const в направлении, противоположном вектору b =(10,8), получаем точку А, в которой достигается минимум функции g( y ). Находим координаты точки А, которая является пересечением двух прямых:

откуда Y 1 = 29/5; Y 2 = -2/5 и Ипользуя теорему 4, находим решение исходной задачи. Так как Y 1* >0 и Y 2* 4), то X 3 =0. Решая систему (1.65), получаем:

ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ ДВОЙСТВЕННОЙ

ЗАДАЧИ ИЗ СИМПЛЕКС-ТАБЛИЦЫ РЕШЕНИЯ ПРЯМОЙ ЗАДАЧИ

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

матрица, обратная для базисной подматрицы расположена на месте единичной матрицы K ( 0 ).

Кроме того, можно показать, что (n+i)-я симплекс-разность матрицы K, определяющей оптимальный план исходной ЗЛП, а j-я симплекс-разность матрицы K (S ) ( j = 1, n ) равна разности между левой и правой частью ограничений двойственной ЗЛП:

Пример 1.17. Решить следующую ЗЛП:

Найти решение задачи двойственной к ЗЛП (1.70).

Так как расширенная матрица системы линейных уравнений (1.70) является К-матрицей, то ЗЛП (1.70) можно решить симплекс-методом. Результаты решения приведены в табл.

На первой итерации получен оптимальный план ЗЛП (1.70).

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

Находим решение ЗЛП (1.71) по формуле

ЭКОНОМИЧЕСКИЙ АНАЛИЗ ЛИНЕЙНЫХ МОДЕЛЕЙ

НА ОСНОВАНИИ ТЕОРИИ ДВОЙСТВЕННОСТИ

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

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

Поясним некоторые вопросы. На этапе постановки задачи производится анализ с целью ответить на вопросы: “Что будет, eсли...?” и (или) “Что надо,..., чтобы...?”. Анализ с целью ответа на первый вопрос называется вариантным анализом, на второй – решениями по заказу.

исходных данных Вариантный анализ бывает следующих видов:

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

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

Многокритериальный анализ – это решение задачи по разным целевым функциям;

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

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

переменных, левых частей ограничений, целевой функции.

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

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

Двойственная к ней имеет вид Оптимальными планами этих задач являются соответственно векторы На основании второй теоремы двойственности Из этой формулы следует, что двойственная переменная является коэффициентом при bi и, значит, показывает, как изменится целевая функция при изменении i-го продукта (ресурса) на 1. В литературе двойственные переменные принято называть двойственными оценками или теневыми ценами.

Анализируя вектор Y, придем к таким выводам. При увеличении запаса продукта А на 1 т доход от реализации продукции увеличится на 1/ тысяч рублей, а при увеличении запаса продукции В на 1 т доход увеличится на 4/3 тысячи рублей. Изменение же запаса С или изменение в соотношениях спроса не приводят к изменению дохода. Продукты А и В при этом являются дефицитными, а продукт С – не дефицитным.

Последний вывод можно было получить, рассуждая иначе. Если некоторый продукт используется не полностью, то есть имеется резерв, знaчит, дополнительная переменная в ограничении для данного продута будет больше нуля. В нашей задаче это дополнительные переменные: S3* = 3/5 т (резерв для продукта С); S4* = 3 т (резерв в разности спроса) и S5* = 2/ т (резерв спроса на продукцию П2). Очевидно, что если бы запас продукта С был бы равен не 5, а 6 т, то резерв был бы равен не 3, а 4 т. при этом не произошло бы увеличения значения целевой функции. Следовательно, для третьего ограничения исходной задачи соответствующая двойственная переменная У3* = 0. Аналогично, У4* = 0, У5* = 0, что и подтверждается вектором Y.

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

Выясним теперь смысл дополнительных двойственных переменных.

В нашей задаче обе основных переменных Х1* и Х2* вошли в оптимальное решение, поэтому дополнительные переменные У6* и У7* равны нулю. Это следует из теоремы IV (о дополнительной нежесткости). Если бы какая-то из основных переменных исходной задачи оказалась равной нулю (данная продукция нерентабельна), то положительное значение соответствующей дополнительной переменной двойственной задачи указало бы, насколько уменьшится целевая функция при принудительном выпуске единицы данной продукции.

Исследуем теперь, как влияет на полученное оптимальное решение изменение величины прибыли от продажи единицы продукции. Допустим, что прибыль от продажи единицы продукции П1 изменится на величину С1 и станет Тогда в последней (оптимальной) таблице решения исходной задачи симплекс-разности будут иметь вид (Таблица 5):

Полученное решение X останется оптимальным при условии Решая эту систему неравенств, получим, что Это условие определяет пределы изменения С1, при которых сохраняется структура оптимального плана. Если от пределов изменения приращения С1 перейти к пределам изменения самой величины С1, то получим Таким образом, при изменении С1 в пределах будет по-прежнему выгодно выпускать продукцию П1. При этом значение целевой функции будет Если выполнить аналогичные преобразования с С2, то получим откуда – пределы изменения С2, при которых будет выгодно выпускать продукцию П2. Полученные пределы изменения Сj – это, кроме того, пределы справедливости дополнительных двойственных оценок.

Рассмотрим влияние на полученное решение изменения запасов продуктов (ресурсов). Пусть запас исходного продукта А равен (6 + А).

Тогда в последней симплекс-таблице (см. на преобразование вектора a в таблице 5) вектор свободных членов примет вид b будут неотрицательны.

Перейдя к пределам изменения А, получим Найденные пределы показывают границы, в которых может изменяться запас продукта А, чтобы номенклатура выпускаемой продукции (структура оптимального плана) осталась без изменений. А это означает, что при изменении запаса продукта А в найденных пределах оптимальным, то есть обеспечивающим наибольшую прибыль, является выпуск и продукции П1, и продукции П2, только в других количествах. Продукции П необходимо будет выпускать в количестве продукции П2 – в количестве при этом доход будет Следовательно, если увеличить запас продукта А на 1 т (А = 1), то для обеспечения максимизации прибыли выпуск продукции П целесообразно уменьшить до X 1 = 3 тонн, а выпуск продукции П2 – увеличить до X 2 = 13 тонн. Доход от реализации продукции станет равным Полученные пределы изменения правых частей уравнений исходной задачи это и есть пределы справедливости двойственных оценок.

1-5. Для приготовления четырех видов продукции (A, B, C, D) используют три вида сырья. Ресурсы сырья, норма его расхода на единицу продукции и цена продукции заданы в соответствующей таблице 1. Определить план выпуска продукции из условия максимизации его стоимости.

2. Определите статус, ценность каждого ресурса и его приоритет при решении задачи увеличения запаса ресурсов.

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

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

5. На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

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

7. Определите изменение стоимости продукции и количество выпускаемых изделий при увеличении второго вида сырья на Z единиц.

8. Определите оптимальное решение задачи для случая, когда вектор ресурсов задан в виде в -строки.

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

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

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

Z=500, в =(2000,1500,2000).

Z=300, в =(1500,2000, 2000).

Цена ( c ) Z=700, в =(2000,2880,1500).

Цена ( c ) Z=450, в =(2000,1500,700).

Цена ( c ) Z=500, в =(1000,2500,500).

6-10.Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее в1 ед. вещества А, в2 ед. вещества В и в3 ед. вещества С. Количество единиц вещества, содержащегося в 1 кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена 1 кг корма каждого вида.

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

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

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

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

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

6. На сколько уменьшится стоимость рациона и используемое количество кормов при снижении минимального уровня потребления питательного вещества В до Z ед.

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

8. Возможно ли сделать выгодным использование корма, не вошедшего в рацион.

9. На сколько увеличится стоимость рациона при принудительном включении в рацион 1 кг нерентабельного вида корма.

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

B = (400,180,200); Z = 7.

B =(400,180,200); Z = 3.

B =(400,180,200); Z = 11.

B =(400,180,200); Z = 6.

10.

B =(400,180,200); Z = 3.

1.6. Решение ЗЛП двухэтапным симплекс-методом Пример. Рассмотрим задачу Так как ограничения (1.75) рассматриваемой ЗЛП уже имеют вид строгих равенств, то для приведения ее к каноническому виду достаточно только изменить знак функции f (x ) на противоположный и рассмотреть задачу нахождения max(- f (x ) ) = -0.4X1 - 0.3X2 - 0.1X3 - 0.1X5 - 0.2X6 (1.77) при тех же ограничениях (1.75)-(1.76).

Рассмотрим расширенную матрицу А системы уравнений (1.75) Так как матрица А не содержит единичной подматрицы порядка 3, то она не является К-матрицей ЗЛП и, следовательно, к задаче (1.74)-(1.76) не может быть применен симплекс-метод.

Рассмотрим метод отыскания исходного опорного плана (Кматрицы) – метод искусcтвенного базиса.

ПЕРВЫЙ ЭТАП - РЕШЕНИЕ ВСПОМОГАТЕЛЬНОЙ ЗАДАЧИ

Пусть в ЗЛП (1.13)-(1.15) расширенная матрица системы линейных уравнений (1.14) не является К-матрицей. Рассмотрим следующую при условиях переменными вспомогательной задачи (ВЗ) (1.78-1.80). Обозначим PM множество планов ВЗ. Очевидно, что множество PM 0, так как вектор сверху, следовательно, ВЗ (1.78-1.80) всегда разрешима, т.е. существует Рассмотрим расширенную матрицу системы (1.79) которая является К-матрицей ВЗ (1.78-1.80), т.е. ВЗ может быть решена симплекс-методом.

Предположим, что ВЗ решена симплекс-методом, на S-й итерации которого получен ее оптимальный опорный план определяемый К-матрицей ВЗ.

Очевидно, что матрица равносильной системе (1.14).

Теорема 1.7. Если X n ) является опорным планом ЗЛП (1.13)-(1.15), если ( X M ) < 0, то множество планов ЗЛП (1.13)-(1.15) пусто.

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

1. На S-й итерации симплексного метода ни одна из искусственных переменных не является базисной, ( N i( S ) n + i, i = 1, m ), т.е.

матрица A ( S ) = K (S ) (1.64) является К-матрицей ЗЛП (1.13)-(1.15), а план X = ( X 1,..., X n ) – опорным планом ЗЛП (1.13)-(1.15), определяемым этой К-матрицей.

2. На S-й итерации симплексного метода в числе базисных оказались искусственные переменные, например, Тогда вектор X M является вырожденным оптимальным опорным планом вспомогательной задачи линейного программирования, а матрица A ( S ) (1.64) содержит p < m единичных столбцов и не является К-матрицей основной задачи.

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

Для этой цели рассмотрим любую r -ю строку из первых Р строк матрицы A ( S ) ( r = 1, p ).

Среди элементов aijS ) ( j = 1, n ) этой строки есть хотя бы один элемент, отличный от нуля, так как в противном случае ранг матрицы А меньше m.

Выберем этот элемент в качестве направляющего с совершим один шаг метода Жордана-Гаусса преобразования матрицы A ( S ) с выбранным направляющим элементом. В результате базисная искусственная переменная U r будет заменена одной из основных переменных X 1,, X 2,..., X n, а элементы (n + 1) стобца матрицы не изменятся.

После р таких шагов метода Жордана-Гаусса матрица A ( S ) будет преобразована в К-матрицу основной задачи линейного программирования, определяющую ее исходный опорный план Очевидно, этот опорный план будет вырожденным.

3. На S-й итерации симплексного метода в числе базисных оказались искусственные переменные U 1,U 2,..., U p, p m, причем хотя бы одна U i(*) не равна нулю. В этом случае множество Р планов ЗЛП (1.13)-(1.15) пусто.

ВТОРОЙ ЭТАП – РЕШЕНИЕ ИСХОДНОЙ ЗАДАЧИ

Если на первом этапе решение ВЗ закончилось случаем 1 или 2, то можно перейти ко второму этапу – решению исходной задачи.

так как расширенная матрица системы линейных уравнений (1.86) является К-матрицей.

РЕШЕНИЕ ЗАДАЧ

Вернемся к решению задачи из примера в начале темы. Для задачи (1.54)-(1.56) запишем ВЗ:

Результаты первого этапа представлены в табл. 10.

На третьей итерации симплексного метода получен оптимальный план вспомогательной задачи: X M = (200; 0; 0; 37.5; 0; 50; 0; 0; 0), в котором ни одна из искусственных переменных не является базисной, следовательно, вектор X = (200; 0; 0; 37.5; 0; 50) является невырожденным опорным планом исходной задачи, определяемым К-матрицей.

На втором этапе решаем задачу Решение приведено в табл. 11.

На первой итерации (табл. 11.) второго этапа получен оптимальный план исходной задачи X 1 = (0; 0; 12.5; 100; 150) и f X 1* = 40.

Так как ( ) = 0, а вектор a3 не является базисным, то его можно ввести в базис, и при этом в соответствии с формулой (1.31) значение целевой функции не изменится, т.е. на второй итерации можно получить еще один оптимальный план исходной задачи задаваемое формулой Пример 1.19. Решить ЗЛП:

Приведем ЗЛП (1.92) к каноническому виду Расширенная матрица системы линейных уравнений (1.93) не является К-матрицей ЗЛП (1.93), так как не содержит единичной подматрицы.

Запишем вспомогательную задачу для ЗЛП (1.93). Так как матрица A содержит один единичный вектор a3 = (1; 0; 0), то при формулировке ВЗ достаточно ввести лишь две искусственные переменные U1; U2 во второе и третье уравнения системы (1.93).

Итак, ВЗ имеет вид Решение ВЗ приведено в табл 12.

На первой итерации получен оптимальный план.

Так как вектор имеет отличную от нуля искусственную переменную U1 = 36, то множество планов ЗЛП (1.92) пусто в силу несовместности системы уравнений (1.93).

ДОМАШНЕЕ ЗАДАНИЕ

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

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

Пример 2.1. В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19.3 м2площади. На приобретение оборудования предприятие может израсходовать 10 тыс. У.е., при этом оно может купить оборудование двух видов. Комплект оборудования 1 вида стоит 1000 у.е., а II вида—3000 у.е.

Приобретение одного комплекта оборудования 1 вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида — на 3 ед. Зная, что для установки одного комплекта оборудования вида требуется 2 м2 площади, а оборудования II вида — 1 м2 площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции Решение. Составим математическую модель задачи. Предположим, что предприятие приобретет х1 комплектов оборудования 1 вида и х комплектов оборудования II вида. Тогда переменные х1 и х2 должны удовлетворять следующим неравенствам:

Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит По своему экономическому содержанию переменные х1 и х2 могут принимать лишь целые неотрицательные значения, т. е, Таким образом, задача (2.1)-(2.4) представляет собой задачу ЦЛП.

Пример 2.2. Рассмотрим задачу о раскрое из примера 1.3.

Очевидно, что переменные модели Xj ( j = 1,6 ) могут принимать только целые значения и, следовательно, ЗЦЛП будет иметь вид:

min f (x ) = 0,4 X1 + 0,3 X2 + 0,1 X3 + 0,1 X5 + 0,2 X

РЕШЕНИЕ З.Ц.Л.П. МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ

Задачей целочисленного линейного программирования ( ЗЦЛП ) называют следующую:

Найти вектор x E n, максимизирующий линейную форму и удовлетворяющий условиям:

При p = n (p < n) задача (2.5)-(2.8) называется полностью (частично) целочисленной задачей линейного программирования.

Для решения ЗЦЛП обычно применяются методы типа отсечений, например, метод Гомори и методы типа возврата - метод ветвей и границ.

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

В начале любой S-й итерации метода ветвей и границ необходимо иметь:

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

2. Нижнюю границу оптимального значения линейной формы задачи (2.5) - (2.8), (2.9) Z0(s). S = 2,3,....... На первой итерации в качестве Z0(1) можно взять значение функции f ( x ) в любой целочисленной точке x, лежащей внутри области (2.6) (2.7) и (2.9). Если такую точку указать трудно, то можно положить Z0(1) =, но это приводит к значительному увеличению числа Алгоритм S-й итерации метода ветвей и границ.

Пусть в результате S итераций метода получили список из Z задач:

1,2,...,Z и имеем Z0(s).

Шаг 1. Выбираем из списка ЗЛП одну задачу для решения, задачу R (1 R Z) и решаем ее.

Шаг 2. Если задача R имеет решение x R, то переходим к шагу 3.

В противном случае - исключаем задачу R из списка и, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1. При S = 0, то есть на первой итерации, делаем вывод, что исходная задача (2.5)-(2.8) не имеет решения и процесс решения заканчивается.

Шаг 3. Если f ( x R ) > Z0(s), то переходим к шагу 4. В противном случае - задачу R исключаем из списка и, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1.

Шаг 4. Если не все компоненты вектора x R удовлетворяют условиям целочисленности (2.8), то переходим к шагу 5. В противном случае - задачу R из списка исключаем, план x R запоминаем и, полагая Z0(s+1)= f ( x R ), возвращаемся к шагу 1. При S = 0 вектор x является решением и исходной задачи (2.5)-(2.8),(2.9) и процесс решения заканчивается.

Шаг 5. Задачу R выбрасываем из списка, включая в него две новые задачи линейного программирования - задачу (Z+1) и задачу (Z+2). Далее, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1. Процесс разбиения задачи R на часть. Тогда задача Z+1 имеет вид:

Процесс решения продолжаем до тех пор, пока не будут решены все задачи линейного программирования из списка. Тогда решением задачи (2.5)-(2.8) и (2.9) будет Z0(s) на последующей итерации.

В качестве Z0(1) возьмем f ( x ) в точке x =(0,0), то есть Z0(1)=0.

1) В списке задач линейного программирования одна задача задача 1 - (2.10)-(2.11),(2.13),(2.14) Шаг 1. Выбираем задачу 1, решаем ее, получим оптимальный план x Шаг 2. Так как задача 1 имеет конечное решение, то переходим к шагу 3.

Шаг 4. Не все компоненты вектора x удовлетворяют условию целочисленности, поэтому переходим к шагу 5.

Шаг 5. Задачу 1 из списка выбрасываем, включая в него две новые задачи - задачу 2 и задачу 3. Разбиение задачи 1 производим по переменной х1:

Шаг 1. Выбираем из списка одну задачу - задачу 2. Решаем ее, ее оптимальный план x = (1,4), f ( x ) = 6.

Шаг 2. Задача 2 имеет конечное решение, переходим к шагу 3.

переходим к шагу 4.

Шаг 4. Все компоненты вектора x удовлетворяют условию целочисленности, поэтому задачу 2 из списка исключаем, план x запоминаем и, полагая Z0(3) = f ( x Шаг 1. Выбираем из списка ЗЛП задачу 3, решаем ее, получили оптимальный план x = (2, 7 / 3).

Шаг 2. Задача 3 имеет конечное решение, следовательно, переходим к шагу 3.

= 6, то переходим к шагу 4.

Шаг 4. Компоненты вектора x не удовлетворяют условию целочисленности, следовательно, задачу 3 из списка выбрасываем и переходим к шагу 5.

Шаг 5. Вместо задачи 3 включаем в список две задачи - 4 и 5.

Разбиение задачи 3 производим по переменной х2:

Итерация 4. Выбираем из списка ЗЛП задачу 5. Она не имеет решения, следовательно, выбрасываем ее из списка. Полагая Z0(5) = Z0(4), возвращаемся к шагу 1.

Итерация 5. Имеем: 1) Список ЗЛП - задача 5.

план x Шаг 4. Компоненты плана x не целочисленные, следовательно, задачу 4 из списка выбрасываем и, полагая Z0(5) = Z0(6), переходим к шагу 5.

Шаг 5. Задачу 4 выбрасываем из списка, а вместо нее включаем в него две новые ЗЛП, производя разбиение задачи 4 по переменной х1:

выбрасываем, а план x запоминаем.

Полагая Z0(7) = Z0(6) = 6 возвращаемся к шагу 1.

Итерация 7. Имеем: 1) Список ЗЛП - одна задача 7.

Шаг 1. Решаем задачу 7 и получаем оптимальный план x запоминаем.

Все задачи линейного программирования, входящие в список, решены. При этом были найдены три целочисленных оптимальных плана исходной задачи является f ( x ) = 6; x =

ДОМАШНЕЕ ЗАДАНИЕ

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

2.2. Транспортная задача линейного программирования распространенных задач линейного программирования и находит широкое практическое приложение.

Постановка транспортной задачи. Некоторый однородный продукт, сосредоточенный у m поставщиков Аi в количестве аi(i=1..m) единиц соответственно, необходимо доставить n потребителям Вj в количестве bj(j=1..n) единиц. Известна стоимость сij перевозки единицы груза от i-го поставщика к j-му потребителю.

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

Обозначим через хij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке хij единиц груза, то стоимость перевозки составит сijxij.

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

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

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

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

в противном случае - открытой. Для открытой модели может быть два случая:

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

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

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

Транспортная задача имеет n+m уравнений с mn неизвестными.

Матрицу Х=(хij)m,n, удовлетворяющую условиям (2.16)-(2.18), называют планом перевозок транспортной задачи (хij - перевозками).

Определение. План Х*, при котором целевая функция (2.15) обращается в минимум, называется оптимальным.

Теорема 2.1 Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых Pij (i=1..m, j=1..n), где Pij - векторы при переменных хij (i=1..m, векторов j=1..n) в матрице системы ограничений (2.16)-(2.17).

Теорема 2.2 Существует план, содержащий не более m+n- соответствующая таким перевозкам (хij > 0), линейно-независима.

Таким образом, опорный план транспортной задачи содержит m+n- положительных перевозок.

Дадим другое определение опорного плана.

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

МЕТОДЫ СОСТАВЛЕНИЯ ПЕРВОНАЧАЛЬНЫХ ОПОРНЫХ

ПЛАНОВ

Метод Северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.

Схема метода: 1) Полагают верхний левый элемент матрицы Х Возможны три случая:

а) если a1 < b1, то х11=а1, и всю первую строку начиная со второго элемента заполняют нулями.

б) если a1 > b1, то х11 = b1, а все оставшиеся элементы первого столбца заполняют нулями.

в) если a1 = b1, то х11 = а1 = b1, и все оставшиеся элементы первых столбца и строки заполняют нулями.

На этом один шаг метода заканчивается.

2) Пусть уже проделано k шагов, ( k µ ) -й шаг состоит в следующем.

Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это элемент x, µ.

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

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

Пусть элементом с минимальным порядковым номером оказался элемент хij0.

Тогда полагают хij0=min(ai, bj) Возможны три случая:

а) если min(ai, bj) = ai, то оставшуюся часть i-й строки заполняют нулями;

б) если min(ai, bj) = bj, то оставшуюся часть j-го столбца заполняют нулями.

в) если аi=bj, то оставшуюся часть строки и столбца заполняют нулями.

Далее этот процесс повторяют с незаполненной частью матрицы.

Пусть элементом с k-м порядковым номером оказался x µ.

Тогда x µ = min(a, b µ ), где заполняют нулями;

нулями;

заполняют нулями.

МЕТОД ПОТЕНЦИАЛОВ

Для транспортной задачи (ТЗ), как и для любой ЗЛП, существует двойственная к ней задача.

j= i= Обозначим двойственные переменные для каждого ограничения вида (2.21) через Ui (i=1,...,m) и вида (2.22)- Vj (j=1,...,n), тогда двойственная задача Переменные задачи, двойственной к транспортнoй, Ui и Vj называют потенциалами.

Теорема 2.3. Для оптимальности плана X=(Xij)mn ТЗ необходимо и достаточно существования чисел (потенциалов) V1, V2,..., Vn и U1, U2,..., Um таких, что U i + V j C j для i=1,...,m, j=1,...,n, Из теоремы следует: для того, чтобы опорный план был оптимальным, необходимо выполнения следующих условий:

а) для каждой занятой клетки (отличного от нуля элемента матрицы Х) сумма потенциалов должна быть равна стоимости перевозки б) для каждой незанятой клетки (Xij=0) сумма потенциалов должна быть меньше или равна стоимости перевозки единицы груза Таким образом, для проверки плана на оптимальность необходимо сначала построить систему потенциалов. Для построения системы потенциалов используем условие U i + V j = C j, Xij>0.

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

Проверка выполнения оптимальности для незанятых клеток.

Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия (2.27), т.е. суммируем потенциалы тех строк и столбцов, на пересечении которых стоит незанятая клетка. Если для всех незанятых клеток U i + V j C ij, то по теореме (2.3) проверяемый план является оптимальным. Если для некоторых клеток Ui+Vj>Cij, то план является не оптимальным. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину (Ui+Vj)-Cij>0.

Выбор клетки, в которую необходимо послать перевозку.

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

Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком “+”, незанятую клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам.

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

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

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

Пример 2.3. Решить ТЗ:

Решение. Условие баланса выполнено. Следовательно, имеем ТЗ закрытого типа.

Предварительный этап : Находим исходный опорный план X° методом «минимального элемента ».

Число занятых клеток равно 6 и совпадает с рангом матрицы ограничений ТЗ:

Итерация 1. Для проверки полученного опорного плана на оптимальность находим систему потенциалов для занятых клеток ( хij>0).

Для этого, например, полагаем U = 0 ( записываем U = 0 слева в табл. 2.2).

Далее, исходя из занятых клеток (1, 2) и (1, 3), находим V2= С12-U = 4 - 0 = 4, V3= 6 - 0 = 6 (записываем сверху в таблице ). На основе базисной клетки (2, 3) получаем U2=2 - 6 =-4, затем V1= 1-(-4) = 5; U3=3 V4=2.

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

U3+ V1 = 4 > 2, U3+ V3 = 5 > 3, то полученный опорный план не оптимальный. Так как 31= U3+ V1- Cij = 2 = 33, то в любую из клеток, например, в (3,1), проставляем некоторое число 1.

Для того, чтобы не нарушился баланс в 3-ей строке, вычитаем 1 из величины перевозки, стоящей в клетке ( 3, 2), прибавляем к Х12, вычитаем от Х13, прибавляем к Х23 и вычитаем от Х21, т.е. составляем цикл :

(3,1)->(3,2)->(1,2)->(1,3)->(2,3)->(2,1)->(3,1).

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

Максимальное значение 1 равно наименьшему уменьшаемому : 1= 50.

Если 1 взять больше, то получаем отрицательную величину в плане перевозок, а если меньше, то нарушается опорность плана.

Новый опорный план приведен в таблице 2. Находим систему потенциалов. Они записаны в таблице слева и сверху, вычисляем сумму потенциалов для свободных клеток (записаны в левом верхнем углу клетки ). Так как U1+ V4 = 4 > 3, то план Х(1) не является оптимальным. Для построения нового опорного плана проставляем величину 2 в клетку (1,4) и составляем цикл:

(1,4)->(3,4)>(3,1)->(2,1)->(2,3)->(1,3)->(1,4).

Определяем значение 2 =50, при этом две клетки (1,3) и (3, 4) обращаются в нулевые. Следовательно, план Х(2) будет вырожденным. Для дальнейшего решения необходимо оставить нуль в одной из клеток и считать ее за базисную. Целесообразнее нуль оставить в клетке с меньшей стоимостью перевозок, т.е. в клетке (3,4). Новый опорный план приведен в таблице 2. Итерация 3. Число занятых клеток равно 6. Находим значения потенциалов и их сумму для свободных клеток. Критерий оптимальности выполняется:

U + Vj Cij для Хij= 0; i=1,m;j=1,n;

поэтому полученный план является оптимальным :

50 --- 250 --Пример 2.4 Решить задачу:

Решение. Объем ресурсов:80+60+60=200 превышает общие потребности : 30+70+60=160 на 40 ед., следовательно, ТЗ является задачей открытого типа. Вводим дополнительный ( балансовый пункт ) потребления с объемом потребностей c14 = c 24 = c 34 = 0. В результате получаем ТЗ закрытого типа.

Предварительный этап. Находим исходный опорный план x методом ‘‘минимального элемента’’ (см. таблицу 2.5).

клетку с минимальным значением c ij, но так, чтобы не образовалось замкнутого маршрута (цикла). В нашем примере c нельзя, так как образуется цикл:

Поэтому ставим ‘‘0’’ в клетку (3,4) Итерация 1. Проверяем план x на оптимальность. Положив u 1 = 0, находим потенциалы (см. таблицу). Далее находим сумму потенциалов для свободных клеток (они записаны в левом верхнем углу клетки). Так как то полученный опорный план x не оптимальный. Для клеток (1,4) и (3,1) оценки одинаковы:

выбираем любую, например, (1,4). Проставляем в эту клетку 1 и составляем цикл, чередуя знаки ‘‘+’’ и ’’-‘‘; получим 1 = 10. Новый опорный план представлен в таблице (2.6).

табл. 2.6). Сумма потенциалов для небазисных клеток записана в левом верхнем углу. Критерий оптимальности не выполняется для клетки (3,1):

результате получаем 2 = 0.Опорный план x представлен в таблице 2.7.

Итерация 3. Найдя систему потенциалов, убеждаемся в оптимальности плана x (см. таблицу 2.7).

x * = (0, 70, 0, 30, 0, 0, 0, 0, 60). Так как четвертый потребитель фиктивный, то 10 ед. груза останутся у первого поставщика, 30 ед. - у второго.] Пример 2. Методом потенциалов решить следующую ТЗ перевозки между указанными пунктами запрещены.

Решение. Проверяем условие баланса:

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

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

Предварительный этап. Составляем методом ‘‘минимального элемента’’ исходный опорный план x - таблица 2. Итерация 1. Вычисляем потенциалы и проверяем план на оптимальность ( см. таблицу 2.8) т.е. план x составляем замкнутый маршрут. Получаем x приведен в таблице 2. Итерация 2. Проверяем план x на оптимальность:

Так как для всех свободных клеток:

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

Минимальные транспортные расходы составляют 3000.

ДОМАШНЕЕ ЗАДАНИЕ

1.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 60, 30, 45, 25 между пятью видами работ, потребности в специалистах для каждой работы соответственно равны 20, 40, 25, 45, 30 и матрица характеризует эффективность использования специалиста на данной работе.

2. Выпуск продукции на трех заводах составляет 500, 700 и 600, причем затраты на производство единицы равны 9, 8 и 2 соответственно.

Потребности четырех потребителей на эту продукцию составляют 350, 200, 450 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j - му потребителю :

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

3. Строительный песок добывается в трех карьерах с производительностью за день 46, 34 и 40 т. и затратами на добычу одной тонны 1, 2 и 3 руб. соответственно; песок доставляется на четыре строительные площадки, потребность которых составляет 40, 35, 30, 45 т.

Транспортные расходы на перевозку одной тонны песка заданы матрицей :

Недостающее количество песка - 30 т. в день можно обеспечить двумя путями : увеличением производительности а) 1 - го карьера, что повлечет дополнительные затраты в 3 руб. на добычу 1 т.; б) 2 - го с дополнительными затратами в 2 руб. / т.

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

4.Имеется три сорта бумаги в количествах 10, 8 и 5 т., которую необходимо использовать на издание четырех книг тиражом в 8000, 6000, 15000 и 10000 экз. Расход бумаги на одну книгу составляет 0,6; 0,8; 0,4 и 0,5 кг,а себестоимость ( в коп. ) печатания книги при использовании i - го сорта бумаги задается матрицей :

Определить оптимальное распределение бумажных ресурсов.

5. Четыре ремонтные мастерские могут за год отремонтировать соответственно 700, 500, 450 и 550 машин при себестоимости ремонта одной машины в 500, 700, 650 и 600 рублей. Планируется годовая потребность в ремонте пяти автобаз: 350, 350, 300, 300 и 200 машин.

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

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

6.Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из В4 будет завезено 60 единиц груза.

7. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А2 в В4 и из А 3 в В 1 перевозки не могут быть осуществлены, а из А 4 в В будет завезено 40 единиц груза.

8. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А 3 в В 2 и из А4 в В 5 перевозки не могут быть осуществлены, а из А1 в В будет завезено 35 единиц груза.

9. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А2 в В5 перевозки не могут быть осуществлены, а из А2 в В будет завезено 45 единиц груза.

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

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

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

Применим метод ДП к решению двух важных экономических задач.

3.1. Задача распределения капиталовложений Постановка задачи. Планируется распределение начальной суммы средств b0 между N предприятиями. Предполагается, что выделение k-му предприятию в начале планового периода средств в количестве уk приносят доход gk(yk). Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарный доход был максимальным.

Рассмотрим процесс управления некоторой системой k - управляющее решение, принимаемое в состоянии x k1.

Качество процесса (эффективность) оценим количественно целевой функцией Задача оптимизации многошагового процесса (1) состоит в значение целевой функции (2), т.е.

Допустимое управление = ( 1, 2,...., N ), которое доставляет максимальное значение функции (2), называется оптимальным управлением, траектория управлению - оптимальной траекторией.

Представление произвольной оптимизационной задачи в виде (3)проводится по следующему алгоритму:

1) Выбирают способ деления процесса управления системой на шаги, определяется понятие шага, количество шагов N.

2) Вводят понятие состояния, задают множества Wk (k=0..N).

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

функцию g k (x k-1, k ( x k-1 )) для любых x k Wk (k=1..N) и критерий эффективности управления всем процессом, т.е. функцию 6) Выписывают рекуррентное уравнение Беллмана (обратная вычислительная схема) Решение поставленной задачи производится по следующему алгоритму:

I этап - этап условной оптимизации.

II этап - этап безусловной оптимизации.

Решим задачу по следующим данным:

2) Средства выделяются в размерах, кратных 50 млн. руб.

3) Функции gk(yk) заданы в таблице 1.

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

Параметры состояния (кол-во средств, которое осталось нераспределенным к началу К-го шага) b0, b1, b2, b3, b4 и параметры управления (количество средств, выделяемое одному предприятию) по условию 2) являются числами, кратными 50 млн. руб.

Таким образом, фазовые ограничения имеют вид bk Wk ={ 0, 50, 100, 150, 200, 250 }, (k = 0..4).

ограничения на управляющие переменные уk k ={ 0, 50, 100,.....,bk-1 }, (k = 1..4) Уравнение состояния имеет вид bk = bk-1 - yk; (k = 1..4) Целевая функция запишется следующим образом:

Запишем уравнение Беллмана Fk* ( b k-1 ) = max{g k ( yk ) + Fk+1 ( b k-1 yk )} Функцию, стоящую в фигурных скобках последнего равенства, обозначим через Fk ( b k-1, y k ), т.е.

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

Fk ( b k-1, yk ), (k = 1..4) и выполняем условную оптимизацию.

Первые три столбца таблицы 2 являются общими для всех четырех шагов: в первом столбце записано состояние в начале k-го шага, во втором - управление на k-м шаге, в третьем - состояние в конце k-го шага, т.е. в начале (k+1)-го шага, которое определяется на основании уравнения состояния. Например, если bk-1=100 (первый столбец), то допустимые управляющие решения уk равны либо 0, либо 50, либо 100 (второй столбец). Состояния в конце шага определяется по уравнению состояния bk = = bk-1 - yk и принимают значения соответственно 100, 50, 0 (третий столбец).

Первый этап - этап условной оптимизации начинаем с последнего, четвертого, шага.

Условная оптимизация выполнена в четвертом столбце таблицы 2.

Так как функция F4 ( b 3, y4 ) = g4 (y 4 ) монотонно возрастает (см. таблицу 1), то ее максимум достигается при наибольшем значении у4, т.е. у4*(b3) = b при этом оптимизации четвертого шага помещаем во второй и третий столбцы таблицы 3.

Уравнение Беллмана имеет вид:

Условная оптимизация выполнена в 5, 6, 7-м столбцах таблицы 2.

Результат условной оптимизации третьего шага помещен в 4 и столбцах таблицы 3.

Уравнение Беллмана имеет вид:

Условная оптимизация выполнена в 8, 9, 10-м столбцах таблицы 2.

Результаты условной оптимизации второго шага помещены в 6 и столбцах таблицы 3.

Уравнение Беллмана имеет вид:

Условная оптимизация выполнена в 11,12,13-м столбцах таблицы Результат условной оптимизации третьего шага помещен в 8 и столбцах таблицы 3.

F4*(b3) y4*(b3) F3*(b2) y3*(b2) F2*(b1) y2*(b1) F1*(b y1*(b0) bk- Второй этап безусловной оптимизации начинаем с первого шага.

Из 8 и 9 столбцов таблицы 3 получаем, что F1*(b0)=113, b0*= и у1 =100, т.е. максимальный доход, который может быть достигнут при вложении 250 млн. руб. в четыре предприятия, равен 113, при этом первому предприятию следует выделить у1*=100 млн. руб.

На основании уравнения состояния определяем остаток средств к началу второго шага (следующий элемент оптимальной траектории):

Из седьмого столбца таблицы 3 при b1* = 150 определим следующий элемент оптимальной стратегии: у2* = 50, т.е. второму предприятию следует выделить 50 млн. руб.

На основании уравнения состояния определяем b2 *= b1*- у2* = = 150 - 50 = 100 и из пятого столбца таблицы 3 находим у3* = 50, т.е. третьему предприятию следует выделить 50 млн. руб.

b3*= b2*- у3*= 100 - 50 = 50 и из третьего столбца таблицы находим, что у4* = у4*(50)=50, т.е. четвертому предприятию следует выделить 50 млн. руб.

Далее определяем b4*= b3*- у4*= 50 - 50 = 0, т.е. средства будут полностью израсходованы.

Итак, оптимальная стратегия распределения 250 млн. руб. между четырьмя предприятиями имеет вид y = ( у1*= 50, у2*= 50, у3*= 50, у4*= 50) млн. руб.

при этом доход составит 113 млн. руб.

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

Рассмотрим задачу управления запасами при заданном расходе.

Пусть планируемый период разделен на N промежутков времени (дни, месяцы, кварталы и т. д.), в которых задан расход dk (k=1..N). Известны начальный уровень запасов x 0 и зависимость суммарных затрат на хранение и пополнение запасов в данном периоде от среднего уровня запасов и их пополнения. Требуется определить размеры пополнения запасов в каждом промежутке времени для удовлетворения заданного расхода из условия минимизации затрат на весь планируемый период.

Рассмотрим данную операцию управления запасами как Nшаговый (по числу периодов) процесс, понимая под шагом пополнение запасов в данном периоде. Состояние системы x k-1 (пополнение - хранение - расход) будем характеризовать одним параметром хk-1 - уровнем запасов в состоянии x k-1, будем понимать решение о пополнении запасов в количестве k, т.е. шаговое управление заключается в выборе единственной переменной k. Средний уровень запасов на k-м шаге будем характеризовать величиной По условию затраты на k-м шаге процесса являются заданной функцией от среднего уровня запасов и размера пополнения, т.е.

Эффективность всей операции характеризуется целевой функцией, равной сумме затрат на хранение и пополнение запасов на всех N шагах, т.е.

Очевидно, что уровень запасов на начало k+1-го шага определяется следующим образом:

и данное соотношение представляет собой уравнение состояния.

Условия удовлетворения расхода dk на каждом шаге можно выразить следующими неравенствами: x k-1 + k - dk 0, (k=1..N), которые представляют собой ограничения на фазовые координаты хk-1 и на управляющие переменные k. Кроме того, управляющие переменные должны быть неотрицательными, т.е.

k 0, (k=1..N). Таким образом, задача управления запасами в течение заданного N-шагового периода при заданном начальном запасе х0 состоит в следующем: требуется найти вектор доставляющий минимальное значение функции и удовлетворяющий условиям Решить задачу при следующих условиях:

Ежемесячное пополнение запасов не превышает 15 ед. Затраты не зависят от времени и состоят из двух слагаемых:

где ( x k ) = 0,4 x k - затраты на хранение, ( k ) = 5 + 2 k затраты на пополнение (k=1..4).