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

СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СТРОИТЕЛЬСТВЕ Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Маркелова И. В., Данилов А. М.

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СТРОИТЕЛЬСТВЕ»

И.В. Маркелова, А.М. Данилов

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

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

Ключевые слова: строительство, оптимизационные задачи, линейное программирование.

Известны практические задачи [1, 2], при решении которых эффективно использовались методы математического программирования (в частности, для повышения нефтедобычи на Ак-танышском месторождении Татарстана). К сожалению, указанные методы для решения архитектурно-строительных задач используются редко до настоящего времени. Ниже приводится ряд возможных приложений.

1.Оптимальное размещение головных сооружений

Имеются три площадки для размещения головных предприятий: 1, 2 — для забора подземных вод; 3 — для забора поверхностных вод. Требуется разместить головные водопроводные сооружения для подачи воды трём потребителям с заданными расходами: 1 потребитель — Gl = 30000 м3/сутки; 2 потребитель — G2 =20000 м3/сутки; 3 потребитель — G3 =40000 м3/сутки. При

этом максимальные производительности водозаборов для 1-й и 2-й площадки не должны превышать 20000 м3/сутки. Стоимость водозаборных сооружений для поверхностных вод (водозабор, очистные сооружения) — d3 =37 тыс.руб/м3; стоимость водозаборных сооружений для забора подземных вод dx = d2 = 50 тыс. руб/ м3. Расстояния ^ между потребителями и площадками для водозаборных сооружений приведены на рис. 1. Определить оптимальные производительности x, x2, x3 водозаборов и транспортируемое из пункта P в пункт P количество воды x , обеспечивающие наименьшую стоимость сооружений, если подача 1 м3 на 1 км обходится:

a = 25 тыс.руб — с первой площадки; a2 =20 тыс.руб — со второй площадки; a3=10 тыс.руб — с третьей площадки.

Таким образом, целью решения является минимизация целевой функции

f = Z j + ZZ ajx1j ; Z Xj = G, Z Xj = Xj, Xj > 0, x, < 20000, k = 1,2.

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

2. Оптимальное размещение сети культурно-бытового обслуживания Пусть известны численность A населения города и численность В населения, обслуживаемого культурно-бытовыми учреждениями. Должны иметь B=A. Пусть далее:

n — число жилых районов города, j — номера районов, aj — население j-го района, m —

число культурно-бытовых учреждений, bi — численность населения, обслуживаемого культур-

но-бытовым центром, Z b = B (A = Z a = Z b = B), с^ — минимальные затраты времени

Вестник магистратуры. 2014. №5(32). Том I

на передвижение из каждого /-го населённого места в каждый 7-й центр культурно-бытового обслуживания.

Рис. 1. Расстояния между потребителями и площадками для водозаборных сооружений

Требуется определить численность х^ населения /-го жилого района, обслуживаемого

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

Снова пришли к задаче линейного программирования: из условий минимума

требуется определить значения х при ограничениях

f=Ё xj =b-‘ Ё xj = aj’ xj -0 •

3. Распределение выпуска продукции по предприятиям

Предполагается за время Т выпуск I видов продукции Д,ДД на г однородных

предприятиях П,П>.••>П соответственно в количествах N,N. N штук. При этом ни

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

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

Количество выпускаемой продукции должно соответствовать номенклатуре:

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

Здесь целевая функция представляет собой общую стоимость выпущенной продукции. С учетом, что величина a^. b X] представляет собой стоимость часть продукции Ai, выпускаемой предприятием Пi, общая стоимость выпускаемой продукции

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

Как и выше задача свелась к задаче линейного программирования.

Решение указанных задач может производиться известными методами [3. 5]; наиболее распространенным является симплекс-метод (существуют стандартные программы).

1. Данилов А.М., Гарькина И.А.Математическое моделирование сложных систем: состояние, перспективы, пример реализации // Вестник гражданских инженеров. 2012. № 2. С. 333-337.

2. Скачков Ю.П., Данилов А.М., Гарькина И.А.Модификация метода ПАТТЕРН к решению архитектурно-строительных задач // Региональная архитектура и строительство. 2011. № 1. С. 4-9.

3. Жегера К.В., Данилов А.М. Квадратичное программирование при решении оптимизационных задач // Вестник магистратуры. 2014. № 2(29). С. 46-48.

4. Будылина Е.А., Гарькина И.А., Данилов А.М. Декомпозиция динамических систем в приложениях // Региональная архитектура и строительство. 2013. № 3. С. 95-100.

5. Гарькина И.А., Данилов А.М., Домке Э.Р. Промышленные приложения системных методологий, теорий идентификации и управления // Вестник Московского автомобильно-дорожного государственного технического университета (МАДИ). 2009. № 2. С. 77-81.

МАРКЕЛОВА Иветта Владимировна — студент, Пензенский государственный университет архитектуры и строительства.

ДАНИЛОВ Александр Максимович — доктор технических наук, профессор, Пензенский государственный университет архитектуры и строительства.

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

Маркелова, И. В. Приложения линейного программирования к решению архитектурно-строительных задач / И. В. Маркелова, И. А. Гарькина. — Текст : непосредственный // Молодой ученый. — 2014. — № 6 (65). — С. 183-185. — URL: https://moluch.ru/archive/65/10797/ (дата обращения: 08.01.2024).

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

При их решении осуществляется перенос методов исследования из одной отрасли в другую, что позволяет организацию междисциплинарных исследований [1…6].

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

Пусть смесь образуется из компонентов, которые могут входить в её состав в различных пропорциях. Допустим, что свойства каждого компонента и всей смеси в целом можно характеризовать m показателями (содержание питательного вещества, калорийность и т. д.). Обозначим через содержание -го показателя (в единице i—го компонента( и через — содержание того же показателя в единице смеси. Заданием матрицы определяются свойства всех компонентов по указанным m признакам. Обозначим через количество -го компонента, входящего в состав данной смеси.

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

Введём в рассмотрениеnвеличин (), оценивающих единицу соответствующегоi-го компонента (например, цена, себестоимость и т. д.). Оценка смеси будет определяться линейной функцией .

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

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

2. Ограничения, налагаемые на количество единиц i-го компонента, входящего в состав смеси. Эти ограничения могут диктоваться либо ограниченными ресурсами данного компонента, либо другими соображениями. Как правило, они будут выражаться в виде неравенств .

3. Условия не отрицательности .

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

или .

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

[4,7,8]). Большую актуальность приобретают указанные задачи и в связи с утилизацией промышленных отходов при производстве строительных материалов и конструкций.

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

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

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

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

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

Размещение сети культурно-бытового обслуживания. Пусть известны численность населения города и численность В населения, обслуживаемого культурно-бытовыми учреждениями. Должны иметь B=A. Пусть далее: n — число жилых районов города, j — номера районов, — население j-го района, m — число культурно-бытовых учреждений, — численность населения, обслуживаемого культурно-бытовым центром, (), — минимальные затраты времени на передвижение из каждого j—го населённого места в каждый i-й центр культурно-бытового обслуживания.Требуется определить численность населения j-го жилого района, обслуживаемого i-м культурно-бытовым центром, обеспечивающую суммарный минимум времени на передвижение населения к центрам культурно-бытового обслуживания. Снова пришли к задаче линейного программирования: из условий минимума требуется определить значения при ограничениях.

Модульное строительство. Пусть для строительства архитектурных сооружений двух типов имеется 100 модулей. На строительство сооружений первого типа расходуется 2 модуля, а на второй тип — 4 модуля. Составить план производства, обеспечивающий получение наибольшей прибыли, если прибыль от строительства сооружений первого типа составляет 300 тыс. рублей, а от строительства второго типа — 200 тыс. рублей. Причем сооружений первого типа требуется не более 40, а сооружений второго типа — не более 20.

Пусть — количество сооружений первого и второго типа соответственно. Тогда .

Выберем за базисные переменные . Получим

Так что будем иметь

Первое допустимое решение ;.

Увеличения можно достичь путем увеличения за счет увеличения . Но увеличивать можно лишь до тех пор, пока или не обратятся в нуль ( при увеличении в нуль не обратится). Из следует, что при ; при ; то есть можно увеличивать до . При этом . Получим второе допустимое решение.

Введем в базис , исключив . Имеем . Откуда . При этом . Таким образом,

; . Коэффициент при отрицателен. Увеличение лишь уменьшает . Поэтому оптимальным решением является ; тыс.руб.

Распределение выпуска продукции по предприятиям. Предполагается за время Т выпуск l видов продукции на r однородных предприятиях соответственно в количествах штук. При этом ни одно предприятие не может одновременно выпускать несколько видов продукции. Пусть известны: — количество, продукции , выпускаемой на предприятии в единицу времени; — стоимость единицы продукции вида , выпущенной на предприятии . — время работы предприятия по выпуску продукции . Время работы каждого предприятия не должно превышать Т: . Количество выпускаемой продукции должно соответствовать номенклатуре:.Требуется найти такие значения , при которых стоимость выпускаемой продукции будет минимальной. Здесь целевая функция представляет собой общую стоимость выпущенной продукции. С учетом, что величина представляет собой стоимость часть продукции , выпускаемой предприятием , общая стоимость выпускаемой продукции .

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

Решение указанных задач может производиться известными методами; наиболее распространенным является симплекс-метод (существуют стандартные программы)

1. Гарькина И. А., Данилов А. М. Современная общая методология идентификации систем: моделирование свойств материалов / Региональная архитектура и строительство. — 2010. — № 1. — С. 11–13.

2. Гарькина И. А., Данилов А. М. Формализованная оценка качества сложных систем: состояние и перспективы / Региональная архитектура и строительство. — 2012. — № 2. — С. 34–37.

3. Будылина Е. А., Гарькина И. А., Данилов А. М. Моделирование с позиций управления в технических системах / Региональная архитектура и строительство. –2013. — № 2 (16). — С. 138–142.

4. Гарькина И. А., Данилов А. М. Опыт разработки композиционных материалов: некоторые аспекты математического моделирования / Известия ВУЗов. Строительство. — 2013. –№ 8 (656). –С.28–33.

5. Будылина Е. А., Гарькина И. А., Данилов А. М., Махонин А. С. Основные принципы проектирования сложных технических систем в приложениях / Молодой ученый. –2013. — № 5. — С. 42–45.

6. Гарькина И. А., Данилов А. М., Домке Э. Р. Промышленные приложения системных методологий, теорий идентификации и управления / Вестник Московского автомобильно-дорожного государственного технического университета (МАДИ). — 2009. — № 2. — С. 77–81.

7. Гарькина И. А., Данилов А. М., Королев Е. В., Смирнов В. А. Преодоление неопределенностей целей в задачах многокритериальной оптимизации на примере разработки сверхтяжелых бетонов для защиты от радиации / Строительные материалы.– 2006. — № 8. — С.23–26.

8. Гарькина И. А., Данилов А. М., Смирнов В. А. Флокуляция в дисперсных системах/ Системы управления и информационные технологии. — 2008. — № 2.3(32). — С.344–347.

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

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

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

Выд-ют 3 осн. этапа мат-го моделир-я.

На 1-ом этапе формулир-ся цели и задачи исслед-я и пров-ся кач-ое опис-е объекта.

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

На 3-ем этапе осущ-ся проведение расчетов, обработка и ан-з рез-ов

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

Ф-ия, экстремум к-ой ищется, наз-ся целевой ф-ей или критерием эфф-ти.

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

1) n -мерный вектор x = (х₁…х _n ) перем-ых, воздействуя на к-ые можно изменить знач-я цел-ой ф-ии. Вектор х наз-ся планом задачи или вектором упр-я, или стратегией;

2) целевая ф-ия Z = Z ( x ) или F = F ( x ), зависящая от указанных перем-ых и исследуемая на экстремум, тот показатель, который нам нужно оптимизиорвать;

3) ограничения, накладываемые на обл-ть измен-я перем-ых. Эти ограничения берут из реальных условий протекания процессов. Обл-ть изм-я перем-ых Ω(х) представляет собой нек-ую обл-ть n -мерного простр-ва, задаваемое сис-ой ур-ий и (или) нер-в. Обл-ть Ω наз-ют обл-ю допустимых знач-ий, а любой вектор х ‘ Ω – допустимым планом задачи.

Т.о. в общем виде задачу мат-го прогр-ия м. записать след. образом: F ( x ) ® max ( min ), х ‘ Ω.

Оптимальным решением ( или оптимальным планом) задачи ЛП называется решение Х = (х₁, х₂, …, х_п), удовлетворяющее указанным ограничениям, при котором целевая функция принимает оптимальное (максимальное или минимальное) значение.

В зав-ти от того, какой вид имеет цел-ая ф-ия и ограничения, задающие ОДЗ, выд-ют разл. классы задач мат-го прогр-ия.

Если и цел-ая ф-ия явл. линейной, а все ограничения им. вид линейных равенст или неравенст, то задача наз-ся ЗЛП.

Если хотя бы одна из ф-ий оптимизационной задачи не явл-ся лин-ой, то задача наз-ся ЗНП.

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

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

2.Задача линейного программирования. Каноническая и стандартная форма ЗЛП. Геометрический смысл и графическое решение ЗЛП.

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

Если целевая функция исследуется на max , а все неравенства им. вид ≤ , то ЗЛП называется стандартной(нер-ва вида ≥ можно превратить в ≤ *-1 ) , если только равенства – канонической. Любая задача линейного программирования может быть сведена к каноническому виду. Для этого во все ограничения-неравенства необходимо ввести дополнительные переменные x_n ₊ _i , положив:

Общая задача ЛП имеет решение тогда и только тогда, когда соответствующая ей каноническая ЗЛП имеет решение.

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

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

(1.1)

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

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

Если ОДЗ пуста, то ЗЛП реш-я не имеет. Если ОДЗ состоит из единств-ой ( × ), то эта ( × ) и будет явл-ся реш-ем ЗЛП.

Перейдем к геометрической интерпретации целевой функции. Линией уровня целевой функции(линией условия) наз-ся геометрич-ое место точек, в к-ом ф-ия принимает одно и то же знач-е. Если цел. ф-ия линейна, то приравнивая ее к константе: получаем ур-ие прямой. Изменяя знач-е, характеризующее линию ур-ня F ₀ , получим семейство параллельных прямых.

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

Учитывая св-ва градиента направл-е возрастания цел-ой ф-ии хар-ся вектором с с коэфф-ми с₁ и с₂. с = (с₁ ; с₂), перпендикулярному линиям уровня.

При реш-и задачи на min нужно двиг-ся в напр-и –с.

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

1. С учетом системы ограничений строим ОДР W . Если ОДР пуста, то ЗЛП не им. решения, если она сост. из 1(.), то эта (.)-решение ЗЛП, если обл. не вырождена, 2 пункт;

2. Строим вектор с = ( ; ) наискорейшего возрастания целевой функции – вектор градиентного направления.

3. Проводим произвольную линию уровня F = F ₀ (проще всего провести линию F =0, перпендикулярную к вектору с).

4. При решении задачи на максимум перемещаем линию уровня F = F ₀ в направлении вектора с так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точке) (на рис. 1.2 – до точки А₄). В случае решения задачи на минимум линию уровня F = F ₀ перемещают в антиградиентном направлении (на рис. 1.2 – до точки А₁).

5. Определяем оптимальный план х* и экстремальное значение целевой функции F *= f ( x * ).

3.Симплекс-метод решения ЗЛП, его сущность. Алгоритм решения ЗЛП симплекс-методом. Критерий оптимальности решения.

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

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

— способ определения какого-либо первоначального допустимого базисного решения задачи;

— правило перехода к лучшему (точнее, не худшему) решению;

— критерий проверки оптимальности найденного решения.

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

Решить симплексным методом задачу:

Графическое решение задачи представлено на рис.

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

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

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

I шаг. Основные переменные: . Неосновные переменные: .

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

Выразим основные переменные и цел-ую ф-ию через неосновные:

(*) , откуда

Положив неосновные переменные равными нулю, получим базисное решение (0; 0; 18; 16; 5; 21). Т.к. все компоненты найденного реш-я не отрицательны, нач-ое реш-е явл-ся допустимым.

В найденной точке значение функции .

Т.о. если при реш-и задачи на max какая-либо из свободных перем-ых входит в цел-ю ф-ию со знаком «+», то найденное реш-е оптимальным не явл-ся, поскольку сделав эту свободную перем-ую положительной, можно добиться увелич-я цел-ой ф-ии. Поэтому необходимо эту переменную перевести в базисную, а вместо нее сделать свободной какую-либо из базисных перем-ых.

Переводим перем-ую х₂ в базисную.

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

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

Переводим в свободную перем-ую х₅.

II шаг. Основные переменные: . Неосновные переменные: .

Выразим новые основные переменные через новые неосновные, начиная с разрешающего уравнения:

Второе базисное решение – (0; 5; 3; 11; 0; 21).

Выразив линейную функцию через неосновные переменные на этом шаге, получаем: .

Значение линейной функции .

Однако найденное реш-е не является оптимальным, т.к. коэф-т при х₁ > 0 и увеличивая х₁ , получим увелич-е цел-ой ф-ии.

х₃ переводим в свободную, х₁ в базисную перем-ую.

III шаг. Основные переменные: . Неосновные переменные: .

После преобразований получим:

(**)

Базисное решение (3; 5; 0; 5; 0; 12). Выражаем линейную функцию через неосновные переменные: . Проверяем: . Третье допустимое базисное решение тоже не является оптимальным, поскольку при неосновной переменной х₅ в выражении линейной функции через неосновные переменные содержится положительный коэффициент. Переводим х₅ в основную переменную. При определении наибольшего возможного значения для х₅ следует обратить внимание на первое уравнение в системе (**), которое не дает ограничений на рост х₅, так как свободный член и коэффициент при х₅ имеют одинаковые знаки. Из третьего ограничения находим максимально допустимое значение х₅ = 1. Третье уравнение является разрешающим, и переменная х₄ переходит в неосновные.

IV шаг. Основные переменные: . Неосновные переменные: .

После преобразований получим:

Базисное решение (6; 4; 0; 0; 1; 3).

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

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

При определении минимума линейной функции Z возможны два пути:

1) отыскать максимум функции F, полагая F = – Z и учитывая, что ;

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

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

4.Симплекс-таблицы. Запись ЗЛП в виде симплекс-таблицы. Правила пересчета симплекс-таблиц.

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

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

Целевая функция, выраженная через свободные переменные, имеет вид .Построим симплекс-таблицу. Строки симплекс-таблицы соот-ют базисным перем-ым и целевой ф-ии, а столбцы – свободным перем-ым и свободным симплекс-таблицы ограничениям:

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

1. В строке целевой функции нет положительных коэффициентов. Тогда найденное допустимое решение является оптимальным.

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

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

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

1) поменять местами переменные и ;

2) на место разрешающего элемента поставить число ;

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

4) на свободные места разрешающего столбца поставить со знаком «-» соответствующие элементы исходной таблицы, деленные на разрешающий элемент

5) о стальные элементы вычислить по правилу прямоугольника (рис. 2.3):

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

5.Частные случаи симплекс-метода: вырожденное решение, альтернативный оптимум, неограниченность целевой функции.

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

Неединственность оптимального решения (альтернативный оптимум)

Решить симплексным методом задачу при ограничениях:

1 шаг . Основные переменные: х₃, х₄, х₅. Неосновные переменные х₁, х₂:.

2 шаг . Основные переменные: х₁, х₃, х₄. Неосновные переменные х₂, х₅:.

х (1) =(2;0;6;3;0) F = 6-3х₅+9х₂ ® max F ₁ =6

3 шаг . Основные переменные: х₁, х₂, х₄. Неосновные переменные х₃, х₅:.

х (2) =(6;2;0;9;0) F = 6-3х₅+9(2+1/3 x ₅ -1/3 x ₃ )=24-3 x ₃ ® max F ₂ =24

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

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

Положим для удобства х₅ = t , где [0; 9]. Тогда множество оптимальных решений:

x * =(6-1/3 t ; 2+1/3 t ; 0 ; 9- t ; t ). F * = 24

Появление вырожденного базисного решения

Решить симплексным методом задачу при ограничениях:

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

I шаг. Основные переменные: . Неосновные переменные: .

После преобразований получим:

х (1) = (0; 0; 2; 6; 14) – допустимое базисное решение; . Критерий оптимальности на максимум не выполнен, поэтому переводим в основные переменную х₁, так как в выражение для F она входит с положительным коэффициентом: х ₁ = min = 2. Оценочные отношения в двух первых уравнениях совпадают , поэтому в качестве разрешающего можно взять любое из них, например, первое.

II шаг. Основные переменные: . Неосновные переменные: . Получим после преобразований:

х (2) = (2; 0; 0; 0; 2) – вырожденное базисное решение, основная компонента х₄ = 0.

Функция цели, выраженная через неосновные переменные, имеет вид: . Переводя переменную х₂ в основные, получаем: х₂ = min < ¥ ; 0; 1>= 0, поэтому на следующем шаге изменения функции цели не произойдет, D F = 0. Это нарушение принципа улучшения решения, который должен выполняться при использовании симплексного метода, в связи с чем уточним данный принцип: каждый следующий шаг должен улучшить или, в крайнем случае, не ухудшить значение линейной функции.

III шаг. Основные переменные: . Неосновные переменные: . После преобразований получим:

х (3) = (2; 0; 0; 0; 2) – это базисное решение тоже вырождено. Покомпонентно оно совпадает с х (2) , однако формально отличается набором основных переменных. Выражение линейной функции через неосновные переменные имеет вид: .

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

Неограниченность целевой ф-ии

Решить симплексным методом задачу при ограничениях:

На очередном шаге решения этой задачи симплексным методом получаем:

Основные переменные – ; неосновные переменные – ;

Х = (5/3; 7/3; 0; 0; 4) – базисное решение; .

Минимум не достигнут, так как критерий оптимальности на это условие не выполнен: переменная х₃ имеет отрицательный коэффициент в выражении для F . Определяем х₃ = min ( ¥ , ¥ , ¥ ) = ¥ , т.к. в каждое из трех уравнений эта переменная входит с тем же знаком, что и свободный член. Уравнения не ограничивают рост х₃, поэтому и значение функции F неограниченно и отрицательно, т.е. .

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

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

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

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

Рассмотрим ЗЛП в каноническом виде:

(2.7)

Без ограничения общности можно считать, что все . В противном случае умножим соответствующее уравнение на –1. В каждое уравнение введем со знаком «+» свою неотрицательную переменную , и рассмотрим вспомогательную задачу линейного программирования:

(2.8)

Определение оптимальности найденного решения.

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

Возможны следующие случаи.

1. . Тогда можно показать, что допустимое множество исходной задачи (2.7) пусто, т.е. эта задача не имеет решения.

2. , и минимум целевой функции достигается в угловой точке

(2.9)

допустимой области вспомогательной задачи. Тогда

(2.10)

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

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

Если вспомогательная задача (2.8) вырождена, то некоторые из переменных могут оказаться базисными. Тогда эти переменные следует перевести в свободные с помощью холостых шагов симплекс-метода (см. п. 2.3). После этого исходная задача (2.7) решается, как описано выше.

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

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

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

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

(1)

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

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

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

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

(2):

Переменные y ₁ ,… y_m называются двойственными оценками. Из (1), (2) можно показать, что если в качестве прямой принять задачу (2) об определении оптимальных оценок на сырье, то двойственной к ней будет задача (1) об определении оптимального плана выпуска продукции. Имея матем. модель одной из задач, можно построить модель двойственной к ней задачи. Задача, двойственная двойственной, совпадает с исходной, поэтому безразлично, какую задачу принять в качестве прямой, а какую – в качестве двойственной. Свойства двойственных задач:

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

2. Если в прямой задаче неравенство имеет вид , то в двойственной соответственно .

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

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

5. Коэфф-ты целевой ф-ии прямой задачи явл-ся свободными членами ограничений двойственной задачи, и наоборот.

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

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

Основные теоремы двойственности и их экономическое содержание

Теорема1(основное нер-во двойс-ти) Для любых допустимых планов х = и
Y = прямой и двойственной ЗЛП справедливо неравенство F ( x ) Z ( y ), т. е.

(3.3)

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

т. е. имеем неравенство (3.3), которое называется основным неравенством теории двойственности.

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

Теорема 2. (критерий оптимальности Канторовича). Если для некоторых допустимых планов х* и Y* пары двойственных задач выполняется равенство z ( x * ) = f ( y * ), то х* и Y* являются оптимальными планами соответствующих задач.

Доказательство. Согласно основному неравенству двойственности, для любого допустимого плана х прямой задачи и допустимого плана Y* двойственной справедливо неравенство z ( x ) f ( y * ). Но по условию
z ( x * ) = f ( y * ). Отсюда, в силу транзитивности отношений и =, получим z ( x ) z ( x * ). Так как х — произвольный план, то z ( x * ) = max Z , т.е. х* — оптимальный план прямой ЗЛП.

Аналогично доказывается, что план Y* является оптимальным для двойственной задачи.

Экономическое содержание теоремы 3.2 состоит в том, что план производства х и вектор оценок ресурсов Y являются оптимальными, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.

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

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

Рассмотрим пару симметричных двойственных задач представленных выше. Введем доп. переменные х _n ₊ ₁ , . х _n ₊ _m в прямую задачу и y_m ₊ ₁ , . у_т+п в двойственную, приводим модели задач к каноническому виду. Теперь м/у переменными двойственных задач можно установить соответствие, сопоставляя свободнвм переменным одной задачи базисные переменные другой, и наоборот:

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

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

, .

Экономическое содержание: двойственные оценки могут служить мерой дефицитности ресурса. Если они 0, то в силу условия дополняющей жесткости разница между расходом ресурса и его запасом должна = 0, т.е. ресурс является дефицитным и расходуется в процессе производства полностью. Если же расход ресурса < используемого запаса, т.е. ресурс недефицитный, то в силу условия дополняющей жесткости, ее двойственная оценка = 0.

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

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

8.Задача целочисленного программирования. Классификация методов решения ЗЦП. Сущность методов отсечения. Алгоритм Гомори решения полностью целочисленной ЗЦП.

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

При этом J является подмножеством множества N : . Если J совпадает с множеством N ( J = N ), т.е. условие целочисленности наложено на все переменные задачи, то задача называется полностью целочисленной. Если J < N , т.е. не все переменные должны быть целыми, то задача частично целочисленная. Решение, полученное из округления, не всегда дает оптимальное решение ЦЗ, т.к. 1) полученная точка может ОДЗ; 2) в ОДЗ может найтись точка, обеспечивающая более оптимальное значение целочисленной функции. Методы целочисленной оптимизации можно разделить на 2 основные группы: точные и приближенные. К точным относятся методы отсечения и комбинаторные. Это универсальные методы дискретной оптимизации. Кроме них, имеется много специальных точных методов, учитывающих специфику задачи. Однако последние имеют слабую сходимость. Среди приближенных методов наметились два направления:

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

2) использование случайного поиска в сочетании с локальной оптимизацией.

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

1) является линейным

2) полученный нецелочисленный план нарушает это ограничение(отсечение д. отсекать оптим. не целочисл. Решение);

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

Затем задача реш-ся с учетом нового ограничения. В случае необходимости добавляется еще одно ограничение и т. д.

Алгоритм метода Гомори для решения полностью целочисленной ЗЛП:

1. Решается ЗЛП с отброшенным условием целочисленности.

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

3. Строится дополнительное ограничение, отсекающее часть области, в которой содержится оптимальное решение ЗЛП и не содержится ни одного допустимого решения ЦЗ.

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

Алг-м Гомори позволяет за конечное число шагов прийти к оптим-му целочисленному решению, если оно сущ-ет.

Формирование правильного отсечения. После каждой итерации симплекс-метода система ограничений ЗЛП имеет вид

(4.1)

где — множество базисных переменных.

Если выполняется условие оптимальности задачи, то все Находим оптимальное решение. Если, все компоненты оптимального плана целочисленны, то задача решена. Предположим, что некоторые β₀ — нецелые. Пусть компонента i ₀ — нецелая. Рассмотрим i ₀ -равенство системы (4.1), для которой выполняется условие оптимальности, т. е.

(4.2)

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

(4.3)

Так как первое слагаемое равенства (4.3) есть целое число, то, для того чтобы было целым, необходимо, чтобы второе слагаемое также было целым, т. е. Величина

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

В самом деле, величина не может быть отрицательной. Из определения дробной части числа следует, что . Так как
— целое, то из предположения, что > 0, должно следовать , что противоречит определению дробной части числа.

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

(4.4)

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

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

9.Постановка транспортной задачи по критерию стоимости в матричной форме. Открытая и закрытая формы ТЗ. Существование допустимого решения. Отыскание начального распределения поставок методами северо-западного угла и наименьших затрат.

Постановка транспортной задачи по критерию стоимости в матричной форме. Пусть имеется m поставщиков А₁,…А _m , обладающие запасами одного ресурса в количестве а i … a_m . Кроме того, имеется n потребителей этого ресурса В₁,…В _n , потребность каждого из которых составляет b_j , j = 1,… n . Известно, что стоимость перевозки единицы ресурса от i -ого поставщика j -му потребителю составляет с _ij . Требуется найти оптимальный план перевозок, т.е. определить количество х _ij -ого ресурса, перевозимого от i -ого поставщика j -му потребителю т.о., чтобы суммарная стоимость всех перевозок была минимальной.

Для построения экономико-математической модели ТЗ рассмотрим матрицу

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

Матрицу X будем называть матрицей перевозок. Предполагается, что все х _ij ≥ 0. Удельные транспортные издержки (расходы) запишем в форме матрицы С=[ с _ij ] и назовем ее матрицей тарифов.

Для наглядности условия ТЗ можно представить таблицей (табл. 5.1), которую будем называть распределительной.

Запас груза a_i

Затраты на перевозку единицы груза

Потребность в грузе b_j

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

(5.1)

Цель ТЗ — минимизировать общие затраты на реализацию плана перевозок, которые можно представить функцией

Модель ТЗ называют закрытой, если суммарный объем груза, имеющегося у поставщиков, = суммарному спросу потребителей. Если суммарный объем груза < или >суммарного спроса, то модель называют открытой.

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

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

Правило «северо-западного угла». Сущность: распределяем груз, начиная с загрузки левой верхней, условно называемой северо-западной, клетки (1; 1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1; 1) заносим меньшее из чисел a ₁ , b ₁ , т. е. x ₁₁ = min ( a ₁ , b ₁ ). Если a ₁ > b ₁ , т. е. x ₁₁ = b ₁ и 1-ый потребитель В₁ будет полностью удовлетворен. В дальнейшем 1-й столбец таблицы в расчет не принимается; в нем переменные х _ik =0 для i =2, т.Двигаясь вправо по 1-ой строке таблицы, заносим в соседнюю клетку (1; 2) меньшее из чисел a ₁ — b ₁ , и b ₂ , т. е. x ₁₂ = min ( a ₁ — b ₁ , b ₂ ). Если a ₁ — b ₁ < b ₂ , то запасы первого поставщика исчерпаны и 1-ая строка таблицы в дальнейшем в расчет не принимается. Переходим к аналогичному распределению запаса груза 2-го поставщика.

Если a ₁ < b ₁ , т. е. x ₁₁ = a ₁ . При этом запас 1-го поставщика будет исчерпан, а потому х _ik =0 для k = 2, п. 1-ая строка из дальнейшего рассмотрения исключается. Переходим к распределению запасов 2-го поставщика. В клетку (2; 1) заносим наименьшее из чисел (а₂, b ₁ — а₁). Заполнив т.о. клетку (1; 2) или (2; 1), переходим к загрузке следующей клетки по 2-ой строке либо по 2-му столбцу. Процесс распределения по 2-ой, 3-ей и последующим строкам (столбцам) производится аналогично распределению по 1-ой строке или 1-му столбцу до тех пор, пока не исчерпаются ресурсы. Последней заполняется клетка (т; п).

Правило «минимального элемента». Сущность: просматриваются тарифы табл. и в первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать т+п-1 загруженных клеток. В процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0 — «нуль-загрузка», условно считая такую клетку занятой. Однако число 0 записывается в те свободные клетки, которые не образуют циклов с ранее занятыми клетками.

10. Метод потенциалов. Критерий оптимальности решения ТЗ. Экономический смысл оценок свободных клеток. Перераспределение поставок. Определение единственности решения.

Если план транспортной задачи является оптимальным, то ему соответствует система из m + n чисел , удовлетворяющих условиям для и для

Числа называются потенциалами соответственно i -го поставщика и j -го потребителя.

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

1) каждой занятой клетке в распределительной таблице соответствует сумма потенциалов, равная тарифу этой клетки, т. е. ;

2) каждой свободной клетке соответствует сумма потенциалов, не превышающая тарифа этой клетки, т. е.

Доказанная теорема носит название теоремы о потенциалах. На ней основан специальный метод решения ТЗ, названный методом потенциалов.

Согласно этой теореме, определение оптимальности плана проводится => образом:

1) строкам и столбцам транспортной таблицы приписываются потенциалы u_i и v_j , определенные как решение системы уравнений u_i + v_j = с _ij для всех заполненных клеток. Поскольку число уравнений m + n -1 на единицу < числа неизвестных, один из потенциалов выбирается произвольным образом, н-р, = 0, после чего однозначно определяются остальные потенциалы;

2) для всех незаполненных клеток находятся оценки s_ij = c _ij – u_i + v_j . Их экономический смысл: оценка c _ij показывает, как изменится стоимость перевозок при загрузке этой клетки единицей ресурса. Если оценки всех пустых клеток положительны, то найденный план является оптимальным, т.к. в этом случае загрузка любой из пустых клеток вызовет увеличение стоимости перевозок. Если все s_ij > 0, то полученный оптимальный план единственный. В случае если хотя бы одна оценка s_ij = 0, оптимальных планов с одним и тем же значением целевой ф-ции бесчисленное мн-во;

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

1) выбирается клетка с отриц. оценкой, если таких клеток несколько, то клетка, имеющая наименьшую оценку;

2) для выбранной клетки строится цикл, одна из вершин которого находится в этой клетке, а остальные в заполненных клетках. Вершинам цикла поочередно приписываются знаки «+» и «–», начиная с пустой клетки. Знак «+» означает увеличение поставок в этой клетке, «–» – уменьшение.

3) для определения величины перераспределенных поставок выбирается min -ое из значений в клетках со знаком «–»;

4) перераспределяя указанное кол-во ресурсов по вершинам цикла, получаем новый опорный план;

5) определяются новые потенциалы и снова определяются критерии оптимальности.

11.Основные понятия теории игр. Матричная игра с нулевой суммой. Минимаксные стратегии. Цена игры, понятие седловой точки. Нахождение оптимального решения в чистых стратегиях.

Теория матричных игр представляет собой теорию принятия решений в условиях неопределенности. Игра – взаимодействие нескольких лиц, игроков, кот. направлено на достижение нек. конеч. состояние, выигрыш, к которому стремиться каждый из игроков, но не каждый может его получить. Стратегия – несколько вариантов возможных действий, имеющихся у каждого игрока в распоряжении. Сделать ход – выбрать одну из стратегий. Партия – последовательность ходов, приводящих игру к конечному состоянию. По числу возможных стратегий игры делятся на конечные и бесконечные. По числу участников — парная, когда игроков 2-е. Результаты такой игры в зависимости от выбора стратегии игроками могут быть представлены с помощью платежной матрицы (матрица выигрышей) размера m x n , где m и n – число возможных стратегий 1-го и 2-го игроков соответственно, а ее элементы а _ij представляют собой выигрыш 1-го игрока при выборе им стратегии А _i при условии, что 2-ой игрок выбрал стратегию В _j .

Матричная игра с нулевой суммой – игра, в которой выигрыш одного игрока = проигрышу другого.

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

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

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

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

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

Если = = , то это чистая цена игры.

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

– в каждой строке находится минимальный элемент, а среди них берется максимальный;

– в каждом столбце находится максимальный, а среди них берется минимальный;

– если эти два элемента совпадают, то матрица имеет седловую точку, в противном случае нет.

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

12.Смешанные стратегии. Доминирующие и доминируемые стратегии, упрощение матричной игры. Сведение матричной игры к ЗЛП.

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

Смешанной стратегией первого (второго) игрока называется вектор

р = , где

q = , где

Вектор p ( q ) означает вероятность применения i -й чистой стратегии первым игроком ( j -й чистой стратегии вторым игроком).

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

Функция f ( p , q ) называется платежной функцией игры.

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

(6.3)

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

Совокупность оптимальных стратегий и цены игры составляет решение игры.

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

Теорема 1. В смешанных стратегиях любая конечная матричная игра имеет седловую точку.

Теорема 2. Для того чтобы смешанные стратегии р*= , q * = были оптимальными для игроков А и В в игре с матрицей и выигрышем v , необходимо и достаточно выполнения неравенств:

(6.4)

(6.5)

Таким образом, для проверки того, что набор (р*, q*, v ) является решением матричной игры, достаточно проверить, удовлетворяют ли р*, q* неравенствам (6.4) и (6.5) и уравнениям

На основании данной теоремы можно сделать вывод: если игрок А применяет оптимальную смешанную стратегию р*, а игрок В — любую чистую стратегию, то выигрыш игрока А будет не меньше цены. игры.

Аналогично: если игрок В использует оптимальную смешанную стратегию q *, а игрок А — любую чистую стратегию, то проигрыш игрока В не превысит цены игры.

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

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

На основании данной теоремы решение матричной игры можно упростить, выявив при этом доминирование одних стратегий над другими. Так, рассматривая стратегии игрока А, сравниваем соответствующие элементы строк s и t . Если все элементы s -й строки не меньше элементов t -й строки, то выигрыш игрока А при стратегии A_s будет больше, чем при стратегии A_t . В этом случае стратегия A_s доминирует над стратегией A_t . Стратегию A_s называют доминирующей, а стратегию A_t — доминируемой.

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

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

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

Теорема 4. Оптимальные смешанные стратегии р* и q* соответственно игроков А и В в матричной игре с ценой v будут оптимальными и в матричной игре ценой v ‘= bv + c , где b >0.

На основании теоремы 6.5 платежную матрицу, имеющую отрицательные числа, можно преобразовать в матрицу с положительными числами.

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

Пусть имеем игру размерности с матрицей

Обозначим через р*= , q * = оптимальные смешанные стратегии игроков А и В. Стратегия р* игрока А гарантирует ему выигрыш не меньше v , независимо от выбора стратегии В _j игроком В. Это можно записать так:

(6.7)

где

Аналогично стратегия q * игрока В гарантирует ему проигрыш не больше v , независимо от выбора стратегии А _i игроком А, т. е.

(6.8)

где

Поскольку элементы платежной матрицы на основании теоремы 6.5 всегда можно сделать положительными, то и цена игры v > 0.

Преобразуем системы (6.7) и (6.8), разделив обе части каждого неравенства на положительное число v , и введем новые обозначения

, где (6.9)

, где 6.10)

Так как игрок А стремится максимизировать цену игры v , то обратная величина 1/ v будет минимизироваться, поэтому оптимальная стратегия игрока А определится из ЗЛП следующего вида: найти минимальное значение функции при ограничениях (6.9).

Оптимальная смешанная стратегия игрока В определится решением задачи следующего вида: найти максимальное значение функции при ограничениях (6.10).

1. если это необходимо, преобразуем платежную матрицу игры, т.о. чтобы она не содерж. отриц. элементов

2. составляем пару двойствен. Задач и решаем из с-м

3. по найденным значения переменных ЗЛП опред цену игры

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

6. ответ:

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

Пусть на множестве U Í R определена функция f ( x ). Под минимизацией функции f(x) на множестве U будем понимать решение следующей задачи: найти хотя бы одну точку минимума x* и минимум f *= f ( x *) этой функции на множестве U.

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

Существование локальных минимумов функции f(х), отличных от абсолютного, почти всегда затрудняет поиск точек x * Î U *, поэтому многие приближенные методы минимизации применимы только тогда, когда любой локальный минимум f(х) является одновременно и глобальным. Один из классов функций, удовлетворяющих этому условию, составляют унимодальные функции.

Функция f(х) называется унимодальной на отрезке [а; b ], если она непрерывна на [а; b ] и существуют числа α и β, такие, что;

3) при х Î [α; β]

Множество функций, унимодальных на отрезке [а; b ], будем обозначать Q [а; b ].

Для проверки унимодальности функции f(х) на практике обычно используют следующие критерии:

1) если функция f(х) дифференцируема на отрезке [а; b ] и производная f'(х) не убывает на этом отрезке, то f ( x ) Î Q [а; b ].

2) если функция f ( x ) дважды дифференцируема на отрезке [а; b ] и f”(х) ³ 0 при x Î [а; b ], то f ( x ) Î Q [а; b ].

Метод деления отрезка пополам является простейшим последовательным методом минимизации. Он позволяет для любой функции f ( x ) Î Q [а; b ] построить последовательность вложенных отрезков , каждый из которых содержит хотя бы одну из точек минимума х* функции f (х) Пусть e >0 — требуемая точность определения точки х*. Выбрав , построим последовательности , используя рекуррентные формулы:

если (1.1)

если

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

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

Золотое сечение отрезка [а; b ] осуществляется двумя точками:

причем x ₁ есть вторая точка золотого сечения отрезка [а; х₂]. а х₂ — первая точка золотого сечения отрезка [х₁; b ].

Зная одну из точек золотого сечения отрезка [а; b ], другую можно найти по одной из формул

(1.2)

Пусть f ( x ) Î Q [а; b ] и требуется найти точку минимума функции f(х) на [а; b ]. Построим последовательности , следующим образом:

, если (1.3)

если

где — первая и вторая точки золотого сечения отрезка .

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

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

2) вычислить значение f(х) во вновь найденной точке золотого сечения (значение в другой точке уже вычислено на одном из предыдущих шагов);

3) сравнить значения и и найти по формулам (1.3).

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

14.Условие Липшица. Минимизация функций, удовлетворяющих условию Липшица

Метод ломаных является последовательным методом, рассчитанным на минимизацию произвольных (не обязательно унимодальных) функций, удовлетворяющих условию Липшица. Говорят, что функция f (х) удовлетворяет на отрезке [а; b ] условию Липшица, если существует такое число L > 0 (константа Липшица), что

для всех х’, х» Î [а; b ].

Для проверки условия Липшица на практике используют следующий факт: если функция f(х) имеет на отрезке [а; b ] ограниченную производную, то она удовлетворяет условию (1.5), где .

Пусть функция f(х) удовлетворяет на [а; b ] условию Липшица с константой L. Опишем метод ломаных для минимизации f(х).

и реализуем следующую схему вычислений:

Шаг 1 . Вместо пары чисел образуем две новые пары и следующим образом:

где .

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

где .

В результате получим множество, состоящее из трех пар чисел (х, р).

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

где . (1.6)

Полагая х* ≈ , f * ≈ f ( ), получим приближенное решение задачи минимизации. Точность определения f * характеризуется неравенствами .

Геометрически метод ломаных состоит в построении последовательности ломаных, приближающихся к графику функции f(х) снизу и имеющих угловые коэффициенты всех звеньев, равные ± L

15.Методы минимизации функций одной переменной, основанные на вычислении производных функции: метод касательных, метод Ньютона.

Mетод касательных применяется для минимизации выпуклых дифференцируемых функций. Функция f (х) называется выпуклой на отрезке [а; b], если

(1.7)

для произвольных х’, х» Î [а; b] и.

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

Для того, чтобы дважды дифференцируемая на отрезке [а; b] функция f(х) была выпуклой на отрезке [а; b], необходимо и достаточно, чтобы f»[x)≥0 при всех х Î [а; b].

Опишем метод касательных. Пусть f(х) — выпуклая дифференцируемая на отрезке [а; b] функция, причем . Построим последовательности , в соответствии с рекуррентными соотношениями

, (1.8)

при , (1.9)

при .

После п шагов полагаем . Требуемая точность минимизации f(x) считается достигнутой, если производная f'(c) достаточно близка к нулю, т. е. | f'(cп)| £ e , где e >0 — заданное число, характеризующее точность.

Метод касательных имеет простой геометрический смысл: величина сn-1 из (1.8) — это абсцисса точки пересечения касательных к графику f(x), проведенных в граничных точках отрезка

Если условие не выполняется, то

а) х*=а при f’ (а) > 0, f’ (b) > 0;

в) х*=а, если f'(a)=0, и х*=b, если f’(b)=0.

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

Пусть f(x) — выпуклая дважды дифференцируемая на R функция. Выбрав начальное приближение х0, построим последовательность

(1.10)

Считая неравенство | f'(хп)| £ e ( e — достаточно малое число) условием достижения требуемой точности вычислений, положим х* ≈ x_n , f* ≈ f( x_n ).

Оценка скорости сходимости может быть сформулирована следующим образом. Пусть f(x) — дважды дифференцируемая на R функция, причем при всех x Î R. и f»‘(х) удовлетворяет условию Липшица на R с константой L. Тогда, если начальное приближение х0 удовлетворяет условию , то последовательность (1.10) сходится к единственной точке минимума х* функции f(х) на R, причем

16.Постановка задачи минимизации функции многих переменных. Выпуклые множества и выпуклые функции. Квадратичные функции, их представление в матричной форме.

Пусть Е п — п-мерное евклидово пространство арифметических векторов . Множество U Ì Е п называется выпуклым, если вместе с любыми двумя точками оно содержит и отрезок, соединяющий эти точки, т. е.

для всех (2.1)

Функция f ( x ), заданная на выпуклом множестве U, называется выпуклой на этом множестве, если для любых точек и произвольного числа справедливо неравенство

(2.2)

На практике обычно используют следующий критерий выпуклости функции:

Если f (х) — дважды дифференцируемая на выпуклом множестве U функция и матрица ее вторых производных (гессиан) положительно определена при всех x Î U , то функция f(х) является выпуклой на множестве U .

э то утверждение можно сформулировать в более удобном для проверки виде:

Если все угловые миноры матрицы, f»(х) положительны при х Î U, то функция f(х) выпукла на множестве U.

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

Если положить то получим симметрическую матрицу , с помощью которой можно представить квадратичную функцию в виде

(2.3)

где , — векторы-столбцы.

Градиент и матрица вторых производных функции (2.3) равны

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

17.Градиентные методы безусловной минимизации: дробление шага и наискорейший спуск. Эффект оврагов, методы его устранения. Метод сопряженных направлений.

Градиент скалярной функции f ( x ) в некоторой точке x_k направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверхности постоянного значения функции f ( x ), проходящей через точку x_k ). Вектор, противоположный градиенту f ’( x_k ,), антиградиент, направлен в сторону наискорейшего убывания функции f ( x ). Выбирая в качестве направления спуска p_k антиградиент функции f(x) в точке x_k , мы приходим к итерационному процессу вида

(2.4)

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

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

(2.12)

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

или ,

где e — заданное достаточно малое число, после чего полагают .

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

(2.11)

проверяем выполнилось ли условие:

(2.12)

Если условие выполняется, то это новая (.). Если при некотором k условие (2.12) нарушается, то шаг в (2.11) уменьшают (дробят) в заданное число раз до выполнения неравенства (2.12) и продолжают вычисления.

Наискорейший спуск . Процесс, на каждой итерации которого шаг α _k выбирается из условия минимума функции f ( x ) в направлении движения, т. е.

(2.15)

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

Шаг α выбирается из условия минимизации по α функции

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

Пояснение: Находим , найденные подставляем в исходную функцию и полученное Ур-ние решаем на min . Если f ( x ) — квадратичная функция (2.3), то величина α _k может быть найдена в явном виде

(2.16)

Таким образом, для квадратичной функций метод наискорейшего спуска состоит в построении последовательности по формулам (2.14), (2.16).

Овраги . Градиентные методы сходятся со скоростью геометрической прогрессии со знаменателем , зависящим от М и т — равномерных по х оценок сверху и снизу соответственно максимального и минимального собственных чисел матрицы f ’’(х). Если М и т мало отличаются друг от друга — матрица f (х) хорошо обусловлена, — то число q мало и, следовательно, сходимость методов достаточно высокая. Если же , то q близко к единице, и градиентные методы начинают сходиться плохо. Этот факт хорошо интерпретируется геометрически и известен в литературе как «эффект оврагов». Если числа М и т сильно отличаются, то топография поверхностей уровня f ( x )= const имеет овражную структуру.

Траектория градиентного метода характеризуется довольно быстрым спуском на «дно» оврага и затем медленным зигзагообразным движением в точку минимума

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

Пусть функция f (х) имеет вид

, (2.17)

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

можно добиться того, чтобы в новых переменных линии уровня стали сферами. Для этого достаточно принять

Тогда получим преобразование

. (2.18)

В случае, когда f(х) не квадратичная, а достаточно гладкая функция общего вида, выбирают

(2.19)

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

Масштабирование переменных в общем случае приводит к итерационному процессу вида

(2.20)

где матрица В _k зависит от номера итерации.

Методы вида (2.20) часто называют релаксационными. При B_k = Е имеем обычный градиентный метод (2.4).

Сопряженные направления . Два вектора х и у в пространстве Е п называются Н-сопряженными (или сопряженными по отношению к матрице Н) или Н-ортогональными, если (х, Ну)=0.

Сопряженность можно считать обобщением понятия ортогональности. В самом деле, когда Н=Е, векторы х и у ортогональны.

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

Пусть — произвольная начальная точка, a — произвольное начальное направление поиска. Тогда следующую точку определим по формуле

(2.21)

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

(2.22)

Возьмем в качестве точку с координатами (1, 1), а в качестве — вектор . (Здесь вектор в иллюстративных целях взят произвольным, хотя можно было бы начать движение из точки по антиградиенту функции f ( x ) .) Координаты точки в соответствии с формулой (2.21) равны

Для вычисления длины шага, согласно (2.22), получим уравнение

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

18.Относительный экстремум, метод исключения переменных. Метод множителей Лагранжа. Теорема Куна-Таккера.

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

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

-уравнения связи

Точка х*, удовлетворяющая этим условиям явл-ся допустимой.

Допустимая точка х* доставляет относительный локальный минимум функции f(х), если можно указать такое число e >0, что для всех х, удовлетворяющих уравнениям связи и условию , имеет место неравенство

f ( x ) > f ( x *).

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

(*)

где — дифференциалы «зависимых» переменных, — дифференциалами «независимых» переменных. При дифференцировании полным образом уравнений связи, получим что дифференциалы «зависимых» переменных с дифференциалами «независимых» следующим образом:

, (**)

Исключим теперь дифференциалы «зависимых» переменных из уравнений (*) и (**), для этого умножим каждое из уравнений системы (**) на произвольные множители и результаты сложим с уравнением (*), тогда получим следующее равенство:

(***)

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

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

(4.8)

Таким образом, мы получили систему п+т уравнений (4.1), (4.7), (4.8) относительно п+т неизвестных , . Этот результат представляет собой основное содержание метода множителей Лагранжа и позволяет определить множество «претендентов» на решение в задаче на относительный экстремум.

Метод Лагранжа состоит из следующих этапов:

1) составляется функция п+т переменных, которая называется функцией Лагранжа:

;

2) вычисляются и приравниваются нулю ее частные производные по х и l :

3) Составленная система п+т уравнений решается относительно п+т неизвестных , .

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

Теорема (Куна—Таккера) . Предположим, что существует вектор такой, что . Тогда необходимым и достаточным условием оптимальности вектора х*, принадлежащего допустимой области, является существование такого вектора l *, что для всех и имеет место неравенство .

Если функции f (х) и являются дифференцируемыми, то неравенства , где , эквивалентны следующим «локальным» условиям Куна-Таккера:

19.Постановка задачи дробно-линейного программирования. Сведение задачи дробно-линейного программирования к ЗЛП.

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

Предположим, что в допустимой области знаменатель не обращается в 0, т.е. f ( x ) определена на всей области. Тогда можно считать, что знаменатель на всей допустимой области . Данная задача может быть сведена к ЗЛП с помощью замены переменных.

, заменим

Тогда ограничения будут иметь вид:

y ₀ должна быть обязательно базисной, т.к. y ₀ >0.

Предположим, что найдено оптимальное решение ( y ₀ * , y ₁ * . y_n * ) , тогда в силу сделанных замен найдем:

x_j * = y_j * / y ₀ * ; f * ( x )=

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

Квадратичные функция – это функция вида или в матричной форме f ( x )=1/2 ( Qx , x )+( r , x )

Пусть имеется выпуклая квадратичная целевая функция

f ( x )=1/2 ( Qx , x )+( r , x ) min

Тогда задачу кв. прог-ния м. сформулировать => образом: найти min выпуклой кв. ф-ции при ограничениях им. вид линейных нер-в

Составим функцию Лагранжа F ( x , λ )

f ( x )=1/2

;

Перейдем к каноническому виду, тогда локальные условий К-Т принимут => вид

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

21.Метод возможных направлений для задачи нелинейного программирования с линейными ограничениями. Выбор возможного направления(ВН), определение величины шага.

Рассмотрим метод возможных направлений решения задачи минимизации выпуклой дифференцируемой нелинейной функции f (х) на допустимом множестве U, заданном линейными ограничениями

(*) (**)

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

1. Пусть в точке все неравенства и выполняются как строгие. Это означает, что — внутренняя точка допустимого множества U. Тогда

2. Пусть хотя бы одно из неравенств (*), (**) в точке обращается в равенство, т.е. является граничной точкой допустимого множества U. Тогда выбор в соответствии с , вообще говоря, невозможен, так как может оказаться, что точка из (***) при любом > 0 не принадлежит множеству U .

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

Обозначим через и множества индексов, соответствующих ограничениям (*) и (**), которые в точке обращаются в равенства, т. е.

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

Очевидно, и для всех .

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

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

Т.к. вектор ВН д. максимально совпадать с – grad , то угол между и grad д.б. max . т.е. , но т.к. мы находимся в граничной точке, то направление не д.б. направлено из ОДЗ, поэтому угол между и внешней нормалью к границе д.б. ≥ 90, поэтому вектор из ищется как решение следующей задачи линейного программирования:

где внешняя нормаль к границе

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

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

, ,

, ,где .

Для учета дополнительного последнего условия при решении задачи симплекс-методом следует не включать переменные и с одинаковым номером j в число базисных одновременно.

Соотношения , , и , , следуют из представления компонент , , вектора .

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

где минимум берется по всем таким, что , т.е.

(****)

где и — максимальные перемещения, при которых для точки из выполняются соответственно i — e ограничение и j -е ограничение ,т. е.

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

, где

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

Приведем описание k -го шага решения задачи при ограничениях (*), (**) методом возможных направлений.

1. Подставить в неравенства (*) и (**) и определить множества индексов и по формулам

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

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

4. Найти очередное приближение по формуле

При выполнении хотя бы одного из условий или , где e > 0 — число, определяющее точность решения задачи, вычисления завершают, полагая

Любое из равенств , означает, что точка минимума х* функции f (х) на множестве U найдена точно:

22.Методы штрафных и барьерных функций.

Основная идея метода заключается в том, что от задачи условной минимизации мы переходим к задаче безусловной минимизации. Это достигается за счет того что, функция безусловной минимизации строится таким образом, чтобы внутри ОДЗ она совпадала с исходной функцией, а вне области неограниченно возрастала. Рассмотрим задачу отыскания минимума функции f (х) на некотором множестве W . Формально она эквивалентна задаче безусловной минимизации суммы

где — так называемая индикаторная функция:

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

Тогда задача, эквивалентная исходной, записывается так:

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

пределом решений которых при k ® ¥ будет точка минимума функции f(х) на множестве W .

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

Методы внутренних штрафных (барьерных) функций

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

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

В данном случае поиск минимума штрафной функции

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

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

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

1. для любой фиксированной внутренней точки х множества W ;

2. для любой последовательности внутренних точек множества W , сходящейся к какой-либо граничной точке этого множества.

Чаще всего в качестве штрафов рассматриваемого типа для задач

(*) при ограничениях

используют такие функции:

(**) или (***)

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

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

б) при k = l , 2, . начиная с точки , полученной на предыдущей итерации, решается задача безусловной минимизации по х функции

в результате чего определяется очередная точка .

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

Методы внешних штрафных функций

В методах внешних штрафных функций штрафы , сходящиеся при k ® ¥ к индикаторной функции, строят так, чтобы при всех k было

= 0 для х Î W

>0 для x Ï W .

Обычно, как и в методах барьерных функций, полагают

только теперь при и F (х) есть функция, определенная на всем пространстве значений x, равная нулю на множестве W и положительная за его пределами. Для задач с ограничениями вида

наиболее распространены две функции F (х):

,(∆) или ,(∆∆)

где — «срезка» функции :

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

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

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

а) выбираются произвольное начальное приближение и монотонно возрастающая последовательность чисел ;

б) при k =1, 2, . начиная с , решается задача безусловной минимизации по х функции

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

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

,поэтому для достаточно больших k полагают . Критерием достижения требуемой точности может служить неравенство

Решение задач линейного программирования с использованием Python

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

К сожалению, не всегда можно положиться на интуицию. Допустим Вы сотрудник коммерческой фирмы и отвечаете за рекламу. Затраты на рекламу в месяц не должны превышать 10 000 денежных единиц (д.е). Минута радиорекламы стоит 5 д.е., а телерекламы 90 д.е. Фирма намерена использовать радиорекламу в три раза чаще чем телерекламу. Практика показывает, что 1 минута телерекламы обеспечивает объём продаж в 30 раз больший чем 1 минута радиорекламы.

Перед Вами стоит задача определить такое распределение средств между двумя упомянутыми видами рекламы при котором объём продаж фирмы будет максимальным. Вы сначала выберите переменные, а именно месячный объём в минутах на телерекламу — x1, а на радиорекламу —x2. Теперь не трудно составить следующую систему:

30×1+x2 –увеличение продаж от рекламы;
90×1+5×2 – ограничение средств;
x2=3×1 – соотношение времён радио и теле рекламы.

Теперь на время забудем о рекламе и постараемся обобщить изложенное. Таких задач, как приваленная, может быть много, но они имеют следующие общие признаки. Обязательным есть наличие линейно зависящей от переменных функции цели, в нашем случае это 30×1+x2, которая при найденных значениях входящих переменных должна иметь единственное максимальное значение. При этом условие не отрицательности входящих переменных выполняется автоматически. Далее следуют опять-таки линейные равенства и неравенства в количестве, зависящем от наличия условий. Вот мы и сформулировали одну группу задач линейного программирования.

Другую большую группу задач линейного программирования, рассмотрим на примере так называемой транспортной задачи. Допустим Вы сотрудник коммерческой фирмы, которая оказывает транспортные услуги. Есть поставщики товара со складами в разных трёх городах, причём объёмы однородной продукции на этих складах соответственно равны a1, a2, a3. Есть и потребители в других трёх городах которым нужно привести товар от поставщиков в объёмах b1, b2, b3 соответственно. Известны также стоимости доставки с1÷с9 товаров от поставщиков к потребителям, согласно таблице.

Если обозначить через x1…xn количество перевозимого груза, тогда функцией цели будет общая стоимость перевозки:

Условия, которые записываться. в виде неравенств:

Условия, которые записываться. в виде равенств:

x1+x4+x7=b1– сколько надо столько и привезём
x2+x5+x8=b2
x3+x6+x9=b3

Тут дополнительно нужны условия не отрицательности переменных x поскольку они по смыслу не отрицательны и ищется минимум F(x). Эти неравенства не приводим.

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

Выбор библиотек Python для решения типовых задач линейного программирования

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

Оптимизация с библиотекой pulp [1].

Листинг программы для решения задачи «О рекламе»

from pulp import * import time start = time.time() x1 = pulp.LpVariable("x1", lowBound=0) x2 = pulp.LpVariable("x2", lowBound=0) problem = pulp.LpProblem('0',pulp.LpMaximize) problem += 30*x1 +x2, "Функция цели" problem += 90*x1+ 5*x2
В лис тенге программы уже знакомые нам соотношения для максимальной прибыли от рекламы 30*x1+x2, условия ограничения затрат, помеченные для сравнения «1». Мы не забыли и об отношении времён использования радио и теле рекламы, помеченные в лис тенге как «2». Назначение других операторов очевидны, Подробности можно прочесть в [1]. Результаты решения задачи оптимизации с использованием pulp. Результат: x1 = 95.238095 x2 = 285.71429 Прибыль: 3142.85714 Время: 0.10001182556152344 В итоге мы получили значения времён рекламы, при которых ожидаемая прибыль от её использования будет максимальна. Оптимизация с библиотекой cvxopt [2]. Листинг программы для решения задачи «О рекламе». from cvxopt.modeling import variable, op import time start = time.time() x = variable(2, 'x') z=-(30*x[0] +1*x[1])#Функция цели mass1 = (90*x[0] + 5*x[1] = 0) #"3" problem =op(z,[mass1,mass2,x_non_negative]) problem.solve(solver='glpk') problem.status print ("Прибыль:") print(abs(problem.objective.value()[0])) print ("Результат:") print(x.value) stop = time.time() print ("Время :") print(stop - start) По структуре программа аналогична предыдущей, но имеются два существенных отличия. Во-первых, библиотека cvxopt настроена на поиск минимума функции цели, а не на максимум. Поэтому целевая функция взята с отрицательным знаком минус -(30*x[0] +1*x[1]). Полученное вследствие этого отрицательное её значение выведено по абсолютной величине. Во-вторых, введено ограничение на не отрицательность переменных- non_negative. Повлияло ли это на результат мы сейчас у видим. Результаты решения задачи оптимизации с использованием cvxopt. Прибыль: 3142.857142857143 Результат: [ 9.52e+01] [ 2.86e+02] Время: 0.041656494140625 Никаких существенных изменений в сравнении с библиотекой pulp не произошло за исключением время работы программы. Оптимизация с библиотекой scipy. optimize [3]. Листинг программы для решения задачи «О рекламе». from scipy.optimize import linprog import time start = time.time() c = [-30,-1] #Функция цели A_ub = [[90,5]] #'1' b_ub = [10000]#'1' A_eq = [[3,-1]] #'2' b_eq = [0] #'2' print (linprog(c, A_ub, b_ub, A_eq, b_eq)) stop = time.time() print ("Время :") print(stop - start)

Достаточно беглого взгляда на листинг, чтобы понять, что мы имеем дело с принципиально иным подходом к вводу данных. Хотя приведенные в листингах цифры помогают прояснить принцип организации данных, путём сравнения, всё же приведу пояснения. Список c = [-30,-1] содержит коэффициенты функции цели с обратным знаком, поскольку linprog () ищет минимум. Матрица A_ub содержит коэффициенты при переменных для условий в виде неравенств. Для нашей задачи это 90x1+5x2 3x1-x2=0, причём ноль в правой части, помещается в список b_eq.
Результаты решения задачи оптимизации с использованием scipy. optimize.
Fun: -3142.8571428571431 
message: 'Optimization terminated successfully.' 
nit: 2 
slack: array([ 0.]) 
status: 0 
success: True 
x: array ([ 95.23809524, 285.71428571])
Время: 
0.03020191192626953
Здесь более подробно выведены результаты расчётов, но сами результаты те же что и в предыдущих библиотеках.
По результатам решения задачи «О рекламе» можно сделать промежуточный вывод, о том что использование библиотеки scipy. optimize обеспечивает большее быстродействие и рациональную форму исходных данных. Однако без результатов решения транспортной задачи окончательный вывод делать рано.
Привожу решение транспортной задачи, но уже без подробных пояснений, поскольку основные этапы решения уже подробно описаны.
Оптимизация с библиотекой pulp.
Листинг программы для решения транспортной задачи.
from pulp import * import time start = time.time() x1 = pulp.LpVariable("x1", lowBound=0) x2 = pulp.LpVariable("x2", lowBound=0) x3 = pulp.LpVariable("x3", lowBound=0) x4 = pulp.LpVariable("x4", lowBound=0) x5 = pulp.LpVariable("x5", lowBound=0) x6 = pulp.LpVariable("x6", lowBound=0) x7 = pulp.LpVariable("x7", lowBound=0) x8 = pulp.LpVariable("x8", lowBound=0) x9 = pulp.LpVariable("x9", lowBound=0) problem = pulp.LpProblem('0',pulp.LpMaximize) problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели" problem +=x1 + x2 +x3 

Решение транспортной задачи требует минимизации затрат по доставке, поэтому функция цели вводиться со знаком минус, а выводиться по абсолютной величине.
Результаты решения транспортной задачи с использованием pulp.
Результат: 
x1 = 0.0 
x2 = 45.0 
x3 = 0.0 
x4 = 0.0 
x5 = 0.0 
x6 = 30.0 
x7 = 20.0 
x8 = 0.0 
x9 = 0.0 
Стоимость доставки: 
215.0 
Время: 
0.19006609916687012
Оптимизация с библиотекой cvxopt.
Листинг программы для решения транспортной задачи.
from cvxopt.modeling import variable, op import time start = time.time() x = variable(9, 'x') z=(7*x[0] + 3*x[1] +6* x[2] +4*x[3] + 8*x[4] +2* x[5]+x[6] + 5*x[7] +9* x[8]) mass1 = (x[0] + x[1] +x[2] = 0) problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, x_non_negative]) problem.solve(solver='glpk') problem.status print("Результат:") print(x.value) print("Стоимость доставки:") print(problem.objective.value()[0]) stop = time.time() print ("Время :") print(stop - start) 
Результаты решения транспортной задачи с использованием cvxopt.
Результат: 
[ 0.00e+00] 
[ 4.50e+01] 
[ 0.00e+00] 
[ 0.00e+00] 
[ 0.00e+00] 
[ 3.00e+01] 
[ 2.00e+01] 
[ 0.00e+00] 
[ 0.00e+00] 
Стоимость доставки: 
215.0 
Время : 
0.03001546859741211
Оптимизация с библиотекой scipy. optimize.
Листинг программы для решения транспортной задачи.
from scipy.optimize import linprog import time start = time.time() c = [7, 3, 6,4,8,2,1,5,9] A_ub = [[1,1,1,0,0,0,0,0,0], [0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,1,1,1]] b_ub = [74,40,36] A_eq = [[1,0,0,1,0,0,1,0,0], [0,1,0,0,1,0,0,1,0], [0,0,1,0,0,1,0,0,1]] b_eq = [20,45,30] print(linprog(c, A_ub, b_ub, A_eq, b_eq)) stop = time.time() print ("Время :") print(stop - start) 
Результаты решения транспортной задачи с использованием scipy optimize.
fun: 215.0 
message: 'Optimization terminated successfully.' 
nit: 9 
slack: array([ 29., 10., 16.]) 
status: 0 
success: True 
x: array([ 0., 45., 0., 0., 0., 30., 20., 0., 0.]) 
Время: 
0.009982585906982422
Анализ решения двух типовых задач линейного программирования с помощью трёх библиотек аналогичного назначения не вызывает сомнения в выборе библиотеки scipy. optimize, как лидера по компактности ввода данных и быстродействию.
Что нового для использования библиотеки scipy. optimize при решении задач линейного программирования
Получение из исходной матрицы, списка для функции цели, а также заполнение матриц неравенств A_ub и равенств A_eq программно, позволит упростить работу по вводу данных и увеличить размерность исходной матрицы. Это позволить решать реальные задачи оптимизации. Рассмотрим, как это можно сделать на простом демонстрационном примере, не претендующем на идеальность кода.
Заголовок спойлера
import numpy as np from scipy.optimize import linprog b_ub = [74,40,36] b_eq = [20,45,30] A=np.array([[7, 3,6],[4,8,2],[1,5,9]]) m, n = A.shape c=list(np.reshape(A,n*m))# Преобразование матрицы A в список c. A_ub= np.zeros([m,m*n]) for i in np.arange(0,m,1):# Заполнение матрицы условий –неравенств. for j in np.arange(0,n*m,1): if i*n 

Теперь вводиться только сама матрица A и списки правых частей b_ub неравенств и b_ub – равенств.
Результат рaботы программы предсказуем. 
fun: 215.0 
message: 'Optimization terminated successfully.' 
nit: 9 
slack: array([ 29., 10., 16.]) 
status: 0 
success: True 
x: array([ 0., 45., 0., 0., 0., 30., 20., 0., 0.])
Вывод частный
При решении задач линейного программирования целесообразно использовать библиотеку scipy.optimize по методике, приведенной в статье, а матрицы условий заполнять програмно. При этом Вам не понадобятся специальные знания о методах решения оптимизационных задач.
Вывод общий
В последнее время появились разные библиотеки Python решающие аналогичные задачи. Решение о применении той или иной библиотеки часто носит субъективный характер. Поэтому целесообразно проводить их сравнительный анализ для области решаемых Вами задач.
Ссылки

pythonhosted.org/PuLP
cvxopt.org/userguide/modeling.html
docs.scipy.org/doc/scipy/reference/tutorial/optimize.html



Похожие публикации:

Mercusys ms105 как подключить
Как добавить панораму в яндекс бизнес
Как сделать диаграмму в ворде на телефоне
Почему заряженная расческа притягивает электрически нейтральные кусочки бумаги

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

СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СТРОИТЕЛЬСТВЕ Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Маркелова И. В., Данилов А. М.

Похожие темы научных работ по математике , автор научной работы — Маркелова И. В., Данилов А. М.

Текст научной работы на тему «СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СТРОИТЕЛЬСТВЕ»

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

Похожие статьи

Применение метода линейного программирования для решения.

Линейное программирование | Статья в журнале «Молодой. »

Решение интервальной задачи дробно-линейного.

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

Формирование оптимальной производственной программы на.

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

Актуальные экономико-математические методы исследования.

Некоторые прикладные задачи целочисленного.

Оптимизация по условиям Куна — Таккера | Статья в журнале.

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

2.Задача линейного программирования. Каноническая и стандартная форма ЗЛП. Геометрический смысл и графическое решение ЗЛП.

3.Симплекс-метод решения ЗЛП, его сущность. Алгоритм решения ЗЛП симплекс-методом. Критерий оптимальности решения.

4.Симплекс-таблицы. Запись ЗЛП в виде симплекс-таблицы. Правила пересчета симплекс-таблиц.

5.Частные случаи симплекс-метода: вырожденное решение, альтернативный оптимум, неограниченность целевой функции.

Решение задач линейного программирования с использованием Python

Выбор библиотек Python для решения типовых задач линейного программирования

Что нового для использования библиотеки scipy. optimize при решении задач линейного программирования

Вывод частный

Вывод общий

Ссылки

Добавить комментарий Отменить ответ