Задачи математического программирования

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

К оглавлению…

Математическое программирование (МП) является одной из важнейших частей математической дисциплины «Математическое программирование» (МП).

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

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

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

Предмет математическое программирование

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

К оглавлению…

Задача1.1. (Задача планирования работы предприятия)

К оглавлению…

Предприятие может выпускать Задачи математического программирования видов продукции. Прибыльность единицы продукции Задачи математического программирования составляет Задачи математического программирования условных единиц. В производстве используется m видов ресурсов (сырье, рабочая сила, финансы и т.д.). Наличие Задачи математического программирования-го ресурса Задачи математического программирования ограничено запасом Задачи математического программирования. Расход ресурса Задачи математического программирования на производство изделия Задачи математического программирования составляет Задачи математического программирования. Требуется определить план работы предприятия по объемам Задачи математического программирования выпускаемой продукции таким образом, чтобы суммарная прибыль была максимальной.

Составим математическую модель данной задачи. Целевая функция будет иметь вид

Задачи математического программирования

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

Задачи математического программирования

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

Задача №1.2. (Задача о диете)

К оглавлению…

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

Задача о диете является одной из первых задач ИО.

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

Задачи математического программирования

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

Задачи математического программирования

Задача №1.3. (Задача о рюкзаке)

К оглавлению…

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

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

Задачи математического программирования

Вторая функция

Задачи математического программирования

Ограничения имеют вид

Задачи математического программирования

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

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

Примеры 1.1 и 1.2 являются типичными задачами ЛП. Пример 1.3 к задачам ЛП не относится. Подобные задачи выделяют в раздел многокритериальной оптимизации, которая в ряде аспектов смыкается с теорией игр.

Задачи ЛП являются математическими моделями многочисленных задач технико-экономического содержания. Основные результаты по решению задач ЛП были получены в 30-е — 40-е годы XX века. Развитие ЛП связано с именем американского ученого Дж. Данцига и советского математика и экономиста Леонида Витальевича Канторовича. Именно работа Канторовича 1939 года «Математические методы организации и планирования производства» сыграла основополагающую роль в развитии ЛП и в целом МП. За исследования в области экономики Л.В. Канторовичу в 1975 году была присуждена Нобелевская премия.

Решение задач по математическому программированию

Математические основы методов математического программирования

К оглавлению…

П.1. Базисные и опорные решения

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

Задачи математического программирования

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

Рассмотрим одну из таких систем

Задачи математического программирования

Составим расширенную матрицу системы и проведем несложные преобразования

Задачи математического программирования

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

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

Задачи математического программирования

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

Задачи математического программирования

Рассмотрим столбцы перед переменными Задачи математического программирования и Задачи математического программирования, как векторы Задачи математического программирования и Задачи математического программирования. Данные векторы образуют базис в двумерном пространстве. Отсюда название переменных Задачи математического программирования и Задачи математического программирования — базисные переменные.

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

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

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

Задачи математического программирования

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

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

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

Задачи математического программирования

В данном примере число базисных решений определяется следующим образом

Задачи математического программирования

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

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

Примеры решения задач по математическому программированию

Задача №2.1.

Найти все опорные решения системы линейных уравнений:

Задачи математического программирования

Решение:

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

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

В четвертом столбце все элементы отрицательные и разрешающий элемент выбрать нельзя.

Остановимся на первом варианте и продолжим процесс далее

Задачи математического программирования

Очевидно, ранг матрицы равен 2, базисные неизвестные — Задачи математического программирования и Задачи математического программирования; свободные — Задачи математического программирования и Задачи математического программирования. Общее решение:

Задачи математического программирования

Базисное решение (7; 0; 0; 1) является опорным.

В данном случае существует

Задачи математического программирования

базисных решений, соответствующих базисным переменным:

Задачи математического программирования

Вариант Задачи математического программирования уже был рассмотрен.

Вернемся к матрице системы, полученной после преобразований:

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

Базисное решение

Задачи математического программирования

опорное.

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

Итак, опорные решения: (7; 0; 0; 1) и

Задачи математического программирования

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

  1. Приводим систему уравнений к виду, когда в столбце свободных членов нет отрицательных чисел.
  2. В выбранном столбце Задачи математического программирования в «конкурсе» на звание «разрешающий элемент» участвуют только положительные элементы.
  3. Каждый элемент в столбце свободных членов, делим на соответствующий ему элемент столбца Задачи математического программирования.
  4. Выбираем из полученных соотношений наименьшее Задачи математического программирования.
  5. Элемент, для которого отношение, полученное в пункте 3, наименьшее, является разрешающим элементом.

П. 2. Свойства выпуклых множеств

Рассмотрим некоторые свойства выпуклых множеств.

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

Свойства выпуклых множеств.

1) Пересечение любой совокупности выпуклых множеств есть выпуклое множество.

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

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

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

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

2) Через каждую точку границы выпуклого множества на плоскости проходит по крайней мере одна опорная прямая, имеющая общую точку с границей, но не рассекающая это множество (на рис. 2.1 Задачи математического программирования — опорные прямые).

Задачи математического программирования

3) Замкнутое выпуклое множество есть пересечение конечного числа замкнутых полупространств.

Пересечение конечного числа замкнутых пространств назовем выпуклым многогранником.

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

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

Перед тем, как изложить основные свойства задачи ЛП, изложим основные формы записи общей задачи ЛП.

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

Заказать работу по математическому программированию

Рассмотрим следующую задачу

Задача №2.2.

Задачи математического программирования

Поставим задачу — привести систему неравенств (*) к системе уравнений.

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

Задачи математического программирования

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

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

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

Задачи математического программирования

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

Задачи математического программирования

где

Задачи математического программирования

матрица строка,

Задачи математического программирования

матрица столбец переменных

Задачи математического программирования

матрица столбец свободных членов,

Задачи математического программирования

матрица системы.

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

Задачи математического программирования

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

Задачи математического программирования
Задачи математического программирования

Сформулируем свойства задачи:

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

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

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

Помощь по математическому программированию

Геометрический метод решения задач математического программирования

К оглавлению…

Цель данного параграфа — представить достаточно простой и наглядный способ решения задачи ЛП для случая, когда число независимых переменных не более трех — геометрический метод. На практике наиболее часто геометрический метод применяется в случае, когда переменных две. В дальнейшем ограничимся именно этим числом переменных.

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

Задачи математического программирования

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

Задачи математического программирования

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

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

Рассмотрим применение геометрического метода на примерах.

Задача №3.1.

Для изготовления единицы сплава № 1 требуется металла Задачи математического программирования — 2 единицы, металла Задачи математического программирования — 3 единицы и металла Задачи математического программирования— 4 единицы. Для изготовления единицы сплава № 2 требуется 2, 5 и 2 единицы металлов Задачи математического программирования и с соответственно. Всего запасы металлов Задачи математического программирования и с составляют соответственно 24, 50 и 40 единиц. Прибыль от реализации единицы сплава № 1 — 20 у.е., от реализации сплава № 2 — 30 у.е. Сколько единиц сплавов № 1 и № 2 нужно изготовить, чтобы суммарная прибыль была максимальной.

Решение:

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

Пусть Задачи математического программирования — число единиц сплава № 1, Задачи математического программирования — число единиц сплава № 2.

В этом случае прибыль от реализации сплавов № 1 и № 2 рассчитывается по формуле

Задачи математического программирования

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

Задачи математического программирования

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

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

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

Это удобно сделать следующим образом:

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

и построить их.

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

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

Задачи математического программирования

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

Задачи математического программирования

Построим опорную прямую Задачи математического программирования. данная прямая перпендикулярна вектору Задачи математического программирования.

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

Задачи математического программирования

Координаты точки Задачи математического программирования найдем, решив систему уравнений

Задачи математического программирования

получим

Задачи математического программирования

Найдем максимальное значение целевой функции

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

Задача №3.2.

Для кормления скота используются грубые корма и концентраты. В 1 кг концентратов содержится 0,8 кормовых единиц и 0,06 кг протеина, в 1 кг грубых кормов содержится 0,3 кормовых единиц и 0,05 кг протеина. Суточный рацион должен содержать не менее 12 кормовых единиц и не менее 1,5 кг протеина. Необходимо составить дневной рацион, имеющий минимальную стоимость, если 1 кг концентрата стоит 10 у.е., а 1 кг грубых кормов — 6 у.е.

Решение:

Данная задача является частным случаем задачи о составлении диеты (см. пример 1.2).

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

Задачи математического программирования

Система ограничений —

Задачи математического программирования

Аналогично тому, как это делалось в примере 3.1, изобразим на координатной плоскости Задачи математического программирования область, соответствующую системе ограничений и опорную прямую Задачи математического программирования (рис. 3.3).

Задачи математического программирования

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

Задачи математического программирования

Получим

Задачи математического программирования

Наименьшее значение целевой функции

Задачи математического программирования

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

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

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

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

К оглавлению…

П.1. Геометрическая интерпретация симплексного метода

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

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

Задачи математического программирования

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

Нечто подобное мы проделывали при работе с геометрическим методом (см. рис. 4.1).

Задачи математического программирования

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

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

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

Задачи математического программирования
Задачи математического программирования

Это соответствует простому перебору опорных решений. Что невозможно по техническим причинам.

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

Задачи математического программирования

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

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

  1. Способ определения какого-либо первоначального опорного решения задачи ЛП (рассмотрен в § 2).
  2. Критерий проверки оптимальности решения.
  3. Правило перехода к лучшему (в общем случае не к худшему) решению.

Замечание 4.1. Добавление «не к худшему» связано с тем, что иногда переход от одного плана к другому не дает моментального выигрыша, но в дальнейшем оказывается весьма полезным.

Все три необходимых элемента содержит симплексный метод (Задачи математического программирования) (лат. simplex — простой).

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

Симплексный метод — это метод последовательного улучшения решений задачи Л П.

П. 2. Математические основы симплексного метода

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

Задачи математического программирования

где

Задачи математического программирования

Предположим, что согласно правилу, сформулированному в § 2, найдено некоторое первоначальное решение задачи ЛП

Задачи математического программирования

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

Условие (4.1) можно переписать следующим образом:

Задачи математического программирования

где

Задачи математического программирования

линейно независимые единичные векторы Задачи математического программирования-мерного векторного пространства. Они образуют базис данного пространства.

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

Задачи математического программирования

Каждому из векторов можно поставить в соответствие значение

Задачи математического программирования

Сформулируем главное утверждение данного раздела.

Теорема 4.1. (Теорема об оптимальности плана) Если для некоторого вектора Задачи математического программирования выполняется условие

Задачи математического программирования

то план

Задачи математического программирования

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

Доказательство. Зададим некоторое число Задачи математического программирования > 0. Умножим уравнение (4.3) на Задачи математического программирования и вычтем из уравнения (4.2). Получим

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

По предположению

Задачи математического программирования

Значит

Задачи математического программирования

Что и требовалось доказать.

Из результатов теоремы 4.1 несложно получить утверждение. Следствие 4.1. Если для некоторого плана Задачи математического программирования разложение всех векторов Задачи математического программирования в данном базисе удовлетворяют условию

Задачи математического программирования

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

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

Теорема 4.2. Пусть для задачи ЛП

Задачи математического программирования

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

Следствие 4.2. Если для некоторого плана Задачи математического программирования разложения всех векторов Задачи математического программирования в данном базисе удовлетворяют условию

Задачи математического программирования

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

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

Приведенные теоремы и их сведения составляют теоретическую основу симплексного метода.

С их помощью можно сформировать три основных этапа симплексного метода.

  1. находится любое опорное решение (базис m-мерного пространства) системы уравнений, соответствующих ограничениям задачи ЛП.
  2. Для того, чтобы проверить полученный план на оптимальность, необходимо для каждого вектора Задачи математического программирования определить значение Задачи математического программирования В дальнейшем значение Задачи математического программирования будем называть оценкой вектора Задачи математического программирования. Если в задаче на максимум среди оценок есть отрицательные, то данный опорный план не оптимальный. В задаче на минимум на оптимальность плана указывают положительные оценки.
  3. В случае, если план не оптимальный, согласно результатам теоремы 4.1 и теоремы 4.2, нужно ввести в базис вектор Задачи математического программирования, оценка которого нас не устраивает. При этом целевая функция улучшится на величину Задачи математического программирования. То есть она увеличится в задаче на максимум или уменьшится в задаче на минимум. Если имеется несколько векторов с «плохими» оценками, то для введения в базис выбирается тот, для которого соответствующее значение Задачи математического программирования наибольшее.
Решение задач по линейному программированию

П. 3. Примеры

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

Задача №4.1.

Найти максимальное значение целевой функции

Задачи математического программирования

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

Задачи математического программирования

Решение:

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

Задачи математического программирования

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

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

Задачи математического программирования

Поясним устройство симплексной таблицы.

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

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

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

Третий столбец Задачи математического программирования — это столбец свободных членов.

Последующие столбцы — это координаты векторов Задачи математического программирования.

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

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

Проверим его на оптимальность. Для этого нужно заполнить строку Задачи математического программирования используя формулы

Задачи математического программирования

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

Задачи математического программирования

Обратите внимание, что в строке Задачи математического программирования базисным векторам обязаны соответствовать нулевые оценки. Если это не так, ищите ошибку. Вы неправильно заполнили столбцы «Базис» и Задачи математического программирования.

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

Рассмотрим вектор

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

Рассмотрим вектор Задачи математического программирования. Проведем для него аналогичные вычисления.

Задачи математического программирования

(две оставшихся координаты вектора отрицательны).

Задачи математического программирования

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

Задачи математического программирования

При составлении таблицы 4.2 были проведены следующие преобразования.

  1. Вторая строка осталась неизменной, поскольку разрешающий элемент равен единице, что и требуется.
  2. К первой строке прибавляется вторая, умноженная на четыре (1+ 411).
  3. К третьей строке прибавляется вторая, умноженная на два (III + 211).

Оценим план

Задачи математического программирования

на оптимальность.

Задачи математического программирования

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

Задачи математического программирования

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

Задача №4.2.

Минимизировать функцию

Задачи математического программирования

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

Задачи математического программирования

Решение:

Приведем задачу к каноническому виду

Задачи математического программирования

Составим симплексную таблицу

Задачи математического программирования

Дадим необходимые пояснения.

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

Задачи математического программирования

П. 4. Метод искусственного базиса

В примере 4.2 нам пришлось выбрать вектор наугад. Благодаря некоторому везению автора первый «попавшийся под руку» опорный план оказался

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

Требуется найти минимальное (максимальное) значение линейной функции

Задачи математического программирования

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

Задачи математического программирования

Предположим, что система ограничений не содержит единичной матрицы.

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

Задачи математического программирования

Справедливо следующее утверждение.

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

Задачи математического программирования

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

Задачи математического программирования

является оптимальным планом исходной задачи.

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

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

Задача №4.3.

Найти минимальное значение линейной функции

Задачи математического программирования

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

Задачи математического программирования

Решение:

Так как в системе ограничений нет единичного базиса, составим расширенную задачу.

Задачи математического программирования

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

1) исключить из базиса все искусственные векторы;
2) отыскать (в случае необходимости) оптимальное решение задачи.

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования
Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

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

Оценим теперь план

Задачи математического программирования
Задачи математического программирования

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

Задачи математического программирования

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

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

Задачи математического программирования

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

Задачи математического программирования

В заключение пункта приведем еще одно утверждение.

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

П. 5. Одна из важнейших математических проблем XXI века

В конце девяностых годов XX века выдающийся отечественный математик В.И. Арнольд от имени Международного математического союза написал ряду ведущих математиков мира, предложив им охарактеризовать некоторые проблемы математики в следующем XXI столетии. Сделать это предложение Арнольда вдохновил знаменитый список проблем Гильберта 1900 г.* В ответ на это предложение американский математик Стивен Смейл член национальной АН США выступил в 1997 г. с лекцией по случаю 60-летия Арнольда в Филдсовском институте (Торонто). В ней он сформулировал 18 проблем, которые отбирались по следующим критериям:

1) простая математически точна формулировка;

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

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

Девятой проблемой С. Смейл поставил проблему линейного программирования, которая сформулирована следующим образом.

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

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

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

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

Графическое решение задач линейного программирования

Двойственность в задачах математического программирования

К оглавлению…

П.1. Экономическая интерпретация двойственных задач

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

Первая фирма. Пусть производится Задачи математического программирования видов продукции, при этом используется m видов сырья, запасы которого Задачи математического программирования. При этом известна технология изготовления продукции, согласно которой на производство единицы продукции Задачи математического программирования-ro вида идет Задачи математического программирования единиц ресурса Задачи математического программирования. Цена от реализации единицы продукции Задачи математического программирования-го типа составляет Задачи математического программирования у.е. Требуется составить план выпуска продукции, который обеспечивал бы первой фирме максимальную прибыль.

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

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

Задачи математического программирования

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

Задачи математического программирования

Здесь Задачи математического программирования — количество единиц продукции Задачи математического программирования.

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

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

Задачи математического программирования

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

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

Задачи математического программирования

Рассуждая аналогичным образом, получим систему неравенств

Задачи математического программирования

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

  1. Если одна задача состоит в отыскании минимума целевой функции, то целью другой задачи будет нахождение максимума функции.
  2. Число условий ограничений одной задачи равно числу неизвестных переменных другой задачи.
  3. Коэффициенты в целевой функции одной задачи являются свободными членами в системе ограничений другой.
  4. Матрицы при переменных в системах ограничений задач являются транспонированными друг другу (см. [8]).
  5. При стандартной записи двойственных задач в системе ограничений задачи на максимум все знаки неравенств Задачи математического программирования (использовать запасов не более, чем …), для задачи на минимум Задачи математического программирования (затратить средств не менее, чем…).
  6. В одной и другой задаче имеются условия неотрицательности.

Обычно задачу, которую ставят первой, называют исходной задачей, задачу, которая составляется по исходной задаче, — двойственной задачей (см. табл. 5.1).

Задачи математического программирования

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

Задачи математического программирования

П.2. Теоремы двойственности

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

Теорема 5.1. (первая теорема двойственности) Если из пары двойственных задач одна имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем

Задачи математического программирования

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

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

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

Задачи математического программирования

где

Задачи математического программирования

матрица строка,

Задачи математического программирования

рая удовлетворяет ограничениям

Задачи математического программирования

где

Задачи математического программирования

матрица коэффициентов при переменных,

Задачи математического программирования

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

Задачи математического программирования

При этом ограничения запишутся в виде

Задачи математического программирования

где

Задачи математического программирования

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

Двойственной для задач (5.1) и (5.2) является следующая задача

Задачи математического программирования

Доказательство.

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

Задачи математического программирования

Для каждого вектора Задачи математического программирования существует вектор Задачи математического программирования такой,что

Задачи математического программирования

или

Задачи математического программирования

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

Для оптимального плана

Задачи математического программирования

справедливы соотношения:

Задачи математического программирования

где

Задачи математического программирования

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

Поскольку по предположению план Задачи математического программирования является оптимальным, то согласно теореме 4.1 выполняются соотношения

Задачи математического программирования

где

Задачи математического программирования

Будем искать оптимальный план двойственной задачи (5.4), (5.5) в виде

Задачи математического программирования

Для того, чтобы доказать, что план

Задачи математического программирования

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

1) для вектора Задачи математического программирования справедливы неравенства (5.5), т.е. Задачи математического программирования является решением двойственной задачи;

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

Докажем, что первое условие выполняется для каждого вектора Задачи математического программирования Задачи математического программирования

Задачи математического программирования

Значит, первое условие выполняется.

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

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

С другой стороны, для плана Задачи математического программирования выполняются соотношения

Задачи математического программирования

Умножим обе части (5.10) слева на матрицу Задачи математического программирования, получим

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

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

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

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

Очевидно, что при увеличении прибыльности первого предприятия, описанного в п.1 данного параграфа, второму предприятию будет сложнее (в смысле денежных затрат) перекупить у него ресурсы. Данный факт нашел свое отражение в знаменитом фильме с участием Дж.Фокса «Секрет его успеха». Опуская комедийные повороты сюжета и блестящую игру актеров, можно сказать, что в фильме сталкиваются две экономические концепции. Старое управление крупной компании, столкнувшись с угрозой быть купленной конкурентами, ведет политику на жесткую экономию и сокращение производства. Молодой менеджер, только что окончивший университет, напротив предлагает шаги для быстрого экономического развития, полагая, что ни у кого не хватит средств купить прибыльную, перспективную компанию. В результате он оказывается прав. Следует традиционный happy end, участие в котором, несомненно, принимали труды Канторовича и Данцига.

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

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

Задачи математического программирования

если

Задачи математического программирования

то

Задачи математического программирования

если

Задачи математического программирования

и наоборот,

Задачи математического программирования

если

Задачи математического программирования

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

Задачи математического программирования

Выразим из (5.12) и (5.13) дополнительные переменные.

Задачи математического программирования

Умножим все уравнения (5.14) на соответствующие переменные Задачи математического программирования, а все уравнения (5.15) на Задачи математического программирования. Получим

Задачи математического программирования

Сложим все равенства (5.16) и все равенства (5.17), получим:

Задачи математического программирования

Положим, что планы

Задачи математического программирования
Задачи математического программирования

оптимальные, тогда

Задачи математического программирования

Складывая (5.18) и (5.19), получим

Задачи математического программирования

Поскольку

Задачи математического программирования

то полученное соотношение может выполняться только при условии, что

Задачи математического программирования

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

Задачи математического программирования

Таким образом, утверждение теоремы доказано.

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

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

Согласно результатам теоремы 5.1 оптимальный план двойственной задачи можно получить по формуле

Задачи математического программирования

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

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

Задачи математического программирования

Последние m векторов Задачи математического программирования образуют единичную матрицу Задачи математического программирования.

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

Задачи математического программирования

При этом последние Задачи математического программирования столбцов образуют матрицу Задачи математического программирования которая получена методом присоединения единичной матрицы (см. [8]). Оценки Задачи математического программирования рассчитываются по формуле

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования
Графический метод решения задач линейного программирования

Задача №5.1.

Предприятие выпускает два вида продукции. Для производства единицы продукции первого типа требуется 12 кг ресурсов Задачи математического программирования, 4 кг ресурсов Задачи математического программирования и 2 кг ресурсов Задачи математического программирования. Для производства единицы продукции второго вида затраты ресурсов следующие: Задачи математического программирования. Запасы ресурсов Задачи математического программирования и Задачи математического программирования составляют 264 кг, 148 кг, 280 кг соответственно. Прибыль от реализации единицы первой продукции — 6 у.е., второй — 4 у.е. Требуется поставить для данной задачи двойственную и найти оптимальные значения и оптимальные планы задач.

Решение:

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

Задачи математического программирования

Здесь Задачи математического программирования — количество единиц продукции первого вида, Задачи математического программирования — количество единиц продукции второго вида.

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

Задачи математического программирования

Здесь Задачи математического программирования — теневые цены на ресурсы Задачи математического программирования соответственно.

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

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

Запишем решение двойственной задачи. Согласно теореме 5.1

Задачи математического программирования

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

Задачи математического программирования

Сделаем проверку. Для этого подставим значения Задачи математического программирования в целевую функцию

Задачи математического программирования

П.З. Объективно обусловленные оценки

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

Значения добавленных переменных

Задачи математического программирования

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

Задачи математического программирования

Ненулевой добавочной переменной Задачи математического программирования соответствует переменная Задачи математического программирования.

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

П.4. Несимметричные двойственные задачи

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

В матричной форме несимметричные двойственные задачи записываются следующим образом.

Задачи математического программирования

Для несимметричных двойственных задач справедлива основная теорема двойственности — теорема 5.1.

Заказать работу по линейному программированию

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

К оглавлению…

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

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

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

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

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

Для удобства условия транспортной задачи задают в виде таблицы.

Задачи математического программирования

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

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

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

Пусть Задачи математического программирования — количество продукта, перевозимого от Задачи математического программирования-го поставщика Задачи математического программирования-му потребителю. Целевая функция задачи будет иметь вид:

Задачи математического программирования

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

Задачи математического программирования

Как видно из экономико-математической модели, транспортная задача является частным случаем задачи ЛП.

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

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

то следует ввести фиктивного потребителя. Его потребности будут равны разности

Задачи математического программирования

а цена перевозки ему товара от любого поставщика будет равна нулю.

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

то следует ввести фиктивного поставщика, выделив ему запасы продукта в размере

Задачи математического программирования

Цена перевозки также будет равна нулю.

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

Помощь по линейному программированию

Задача №6.1.

Перевести открытую транспортную задачу (см. таблицу 6.2) в закрытую.

Задачи математического программирования

Решение:

Найдем суммарные запасы.

25 + 5 + 20 + 10 = 60. Найдем суммарные потребности

15 + 5 + 10 + 20 = 50. Таким образом, перед нами открытая задача, в которой запасы больше потребностей. Вводим фиктивного потребителя, выделяем ему 10 единиц продукта. При этом таблица 6.2 преобразуется следующим образом.

Задачи математического программирования

В данной задаче выполняются условия

Задачи математического программирования

Значит открытая транспортная задача сведена к закрытой.

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

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

1) Как составить первоначальный опорный план?

2) Как проверить план на оптимальность?

3) Как в случае, если план не оптимальный, перейти к лучшему (не худшему) плану?

П. 2. Построение первоначального опорного плана

Для транспортной задачи ЛП справедливы следующие утверждения.

Теорема 6.1. Любая закрытая транспортная задача имеет решение.

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

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

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

Существует несколько способов составления первоначального опорного плана.

  1. Метод северо-западного угла. Этот метод состоит в том, что заполнение таблицы 6.1 начинается последовательно с левой верхней ячейки, без учета стоимости перевозок.
  2. Метод наименьшей стоимости. В этом методе из всей таблицы выбирают клетку с наименьшей стоимостью Задачи математического программирования помещают туда наименьшее из чисел Задачи математического программирования или Задачи математического программирования. Если потребности потребителя Задачи математического программирования удовлетворены, то его исключают из рассмотрения. Обратно, если при заполнении клетки Задачи математического программирования израсходованы все запасы, то в дальнейшем распределении поставок не участвует поставщик Задачи математического программирования. После этого выбирают следующую клетку с наименьшей стоимостью и т.д.
  3. Метод двойного предпочтения. Этот метод особенно удобен в случае, когда таблица 6.1 велика. Суть его заключается в следующем. В каждом столбце знаком Задачи математического программирования (или любым другим, как кому захочется) отмечается клетка, имеющая наименьшую стоимость Задачи математического программирования. Затем отмечается клетка, имеющая наименьшую стоимость в строке. В результате появятся клетки, имеющие отметки Задачи математического программирования, клетки, имеющие отметку Задачи математического программирования, и клетки, не имеющие отметок. В клетки Задачи математического программирования, помещают максимально возможные поставки, каждый раз, исключая соответствующих поставщиков или потребителей. Затем заполняются клетки Задачи математического программирования. Затем клетки без отметок с использованием метода наименьшей стоимости.

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

Замечание 6.1. Метод двойного предпочтения лучше именно в среднем. Какой метод окажется лучше в конкретной задаче сказать нельзя.

Задача №6.1 (продолжение).

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

Решение:

Задачи математического программирования

Замечание 6.2. Клетки в добавленном столбце Bs заполняются в последнюю очередь, несмотря на то, что имеют нулевую стоимость.

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

Задачи математического программирования

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

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

Задачи математического программирования

Сделаем максимальную поставку в клетку Задачи математического программирования. Она равна 10 ед. продукта, т.к. 5 ед. продукта из необходимых 15 ед. были получены потребителем Задачи математического программирования от поставщика Задачи математического программирования. Теперь потребности потребителя Задачи математического программирования полностью удовлетворены, столбец Задачи математического программирования не рассматривается. Делаем поставку в клетку Задачи математического программирования. Максимально возможная поставка равна 5 ед. продукта, оставшимся у поставщика Задачи математического программирования. При этом строка Задачи математического программирования в дальнейшем распределении товара не участвует.

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

Остаются незаполненными клетки Задачи математического программирования а также клетки добавочного столбца Задачи математического программирования и Задачи математического программирования. Стоимость перевозки в клетках Задачи математического программирования и Задачи математического программирования одинакова — 4 у.е. На выбор сделаем поставку 15 ед. продукции в клетку Задачи математического программирования. Оставшиеся 10 ед. продукции у поставщика Задачи математического программирования заносим в столбец фиктивного потребителя Задачи математического программирования в клетку Задачи математического программирования.

Первоначальное распределение товара закончено. Общая стоимость перевозок равна

Задачи математического программирования

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

Замечание 6.3. Типичные ошибки при составлении опорного плана появляются из-за того, что решающий забывает, сколько тот или иной поставщик доставил продукта тому или иному потребителю. Для проверки достаточно просуммировать поставки по строкам и столбцам и сравнить их с соответствующими запасами и потребностями, например, для первой строки 10+15 = 25-верно.

Вернемся к решению задачи 6.1. В первоначальном плане перевозок содержится 7 положительных компонент. Согласно утверждению теоремы 6.2 опорный план транспортной задачи должен содержать Задачи математического программирования положительных компонент, т.е. 4 + 5 — 1 = 8. В полученном плане не хватает одной положительной компоненты. Такой план перевозок, в котором число положительных перевозок меньше, чем Задачи математического программирования называется вырожденным опорным планом. Как будет видно в дальнейшем вырожденность не очень «испортит» процесс решения транспортной задачи.

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

Определение 6.1. Циклом называется набор клеток вида Задачи математического программированияЗадачи математического программирования, в котором две и только две соседние клетки расположены в одном столбце или одной строке таблицы, причем последняя клетка находится в том же столбце, что и первая.

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

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

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

П. 3. Оценка плана транспортной задачи на оптимальность (метод потенциалов)

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

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

Задачи математического программирования

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

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

Задачи математического программирования

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

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

2) Получим систему потенциалов из условия

Задачи математического программирования

занятой клетки.

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

Задача №6.1 (продолжение).

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

Решение:

Перепишем таблицу 6.5 в следующем виде.

Задачи математического программирования

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

Задачи математического программирования
Задачи математического программирования

Зная потенциалы Задачи математического программирования определим потенциалы Задачи математического программирования.

Задачи математического программирования

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

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

Делаем нулевую фиктивную поставку в клетку Задачи математического программирования со стоимостью перевозки 2 у.е. Определяем оставшиеся потенциалы:

Задачи математического программирования

Система потенциалов построена.

Составим оценочную матрицу Задачи математического программирования, рассчитывая ее элементы по формулам:

Задачи математического программирования

и т.д.,

Задачи математического программирования

Получим

Задачи математического программирования

Индекс «0» означает номер итерации.

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

П. 4. Переход от одного опорного плана транспортной задачи к другому

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

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

При перераспределении в клетках со знаком «-» вычитаем значение By из величины перевозки, в клетках со знаком «+» прибавляем.

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

Задача №6.1 (продолжение).

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

Решение:

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

Задачи математического программирования

В матрице (6.4) знаком «•» обозначается незанятая клетка. Рассмотрим два цикла, с помощью которых делаются поставки в клетки Задачи математического программирования и Задачи математического программирования.

Задачи математического программирования

Определим экономию от поставки в клетку Задачи математического программирования. В полученном цикле две вершины с отрицательными отметками Задачи математического программирования и Задачи математического программирования. Получим

Задачи математического программирования

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

Задачи математического программирования

Делаем поставку в клетку Задачи математического программирования. Для этого в вершинах цикла, отмеченных знаком «+», добавим к поставкам 10 ед. продукта, в вершинах, отмеченных знаком «-» отнимем 10 ед. продукта. Получим

Задачи математического программирования

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

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

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

Задачи математического программирования

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

Задачи математического программирования

В матрице Задачи математического программирования остался отрицательный элемент Задачи математического программирования. Составляем цикл с началом в клетке Задачи математического программирования.

Задачи математического программирования

Поскольку Задачи математического программирования, то экономия от поставки равна нулю, т.е. план не ухудшится.

Задачи математического программирования

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

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

Задачи математического программирования

Делаем поставку в клетку Задачи математического программирования.

Задачи математического программирования

Найдем экономию от данной поставки

Задачи математического программирования

Получим (мнимый ноль в клетке Задачи математического программирования вычеркиваем)

Задачи математического программирования

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

Задачи математического программирования
Задачи математического программирования

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

Найдем общую стоимость перевозок

Задачи математического программирования

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

Задачи математического программирования

За три итерации была достигнута экономия

Задачи математического программирования

Тогда

Задачи математического программирования

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

Проведем небольшой анализ решения.

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

Задачи математического программирования

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

Контрольная работа линейное программирование

Элементы целочисленного математического программирования

К оглавлению…

ПЛ. Постановка задачи целочисленного математического программирования

В некоторых экономико-математических моделях к традиционным ограничениям добавляется требование целочисленного решения. Действительно, если речь идет о производстве различных типов тракторов, то ответ «нужно произвести 6,5 штук тракторов первого типа» вызовет недоумение. К типичным экономическим задачам, в которых решение должно даваться в целых числах, относятся задачи об оптимальном раскрое материала, об оптимальном использовании оборудования и т.д.

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

Найти минимальное (максимальное) значение линейной функции

Задачи математического программирования

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

Задачи математического программирования

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

П.2. Методы отсечения

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

В работе Э.А. Мухачевой и Г.Ш. Рубинштейна методы отсечения удачно сравниваются с работой скульптора, который для изготовления скульптуры берет каменную глыбу и отсекает от нее все ненужное. В качестве глыбы в задачах целочисленного программирования выступает многогранник решений (см. рис. 7.1).

Задачи математического программирования

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

Остановимся подробнее на методе, предложенном американским математиком Гомори. Рассмотрим его на примере.

Линейное программирование в Excel

Задача №7.1.

Методом Гомори решить следующую задачу. Для приобретения оборудования по переработке молока фермер выделяет 18 ден. ед. Оборудование должно быть размещено на территории, не превышающей 6 соток. Можно заказать оборудование двух видов Задачи математического программирования и Задачи математического программирования. Единица оборудования Задачи математического программирования стоит 4 ден. ед. и занимает площадь в 1 сотку. Ее использование приносит доход в 3 ден. ед. Единица оборудования Задачи математического программирования стоит 6 ден. ед., занимет площадь 2 сотки и приносит доход 2 ден. ед.

Фермер не может приобрести более 5 ед. оборудования Задачи математического программирования и более 4 ед. оборудования Задачи математического программирования.

Решение:

Экономико-математическая модель сформулированной задачи имеет вид:

Задачи математического программирования

где Задачи математического программирования — число единиц оборудования Задачи математического программирования и Задачи математического программирования соответственно.

Решим задачу (7.1) (воспользуемся симплексным методом решения).

Задачи математического программирования

Обозначим Задачи математического программирования и Задачи математического программирования целые части чисел Задачи математического программирования и Задачи математического программирования соответственно. Величины

Задачи математического программирования

неотрицательны.

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

Задачи математического программирования

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

В нашем случае

Задачи математического программирования
Задачи математического программирования

Значит,

Задачи математического программирования

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

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

Задачи математического программирования

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

Задачи математического программирования

Полученное решение задачи (7.3)

Задачи математического программирования
Задачи математического программирования

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

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

Задачи математического программирования

Новое ограничение имеет вид

Задачи математического программирования

Сформулируем новую задачу

Задачи математического программирования

Решая задачу (7.4) симплексным методом получим

Задачи математического программирования
Задачи математического программирования

В плане Задачи математического программирования нет дробных компонент. Задача решена.

П.З. Комбинаторные методы

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

Задача №7.2.

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

Задачи математического программирования

Решение:

Решая исходную задачу (7.5), получим

Задачи математического программирования

Данная задача не обладает целочисленным планом, поскольку Задачи математического программирования -дробное. Так как оптимальное целочисленное решение не должно содержать полосу 4 < Задачи математического программирования< 5, исключаем ее. Получим две новые задачи:

Задачи математического программирования

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

Решая задачу II, получим

Задачи математического программирования

Разобьем задачу II на две задачи линейного программирования IV и V, исключив полосу 0 < Задачи математического программирования < 1.

Задачи математического программирования

Решая задачу IV, получим

Задачи математического программирования

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

Решаем задачу V. Получаем

Задачи математического программирования

Решение нецелочисленное. Исключаем из рассмотрения полосу 3 < Задачи математического программирования <4. Получаем две новые задачи:

Задачи математического программирования

Условия задачи VII являются противоречивыми.

Решая задачу VI, получим

Задачи математического программирования

Несмотря на то, что решение задачи VI нецелочисленное, нет смысла продолжать ее решение, поскольку уже был получен результат

Задачи математического программирования

Решение закончено.

Задачи математического программирования
Курсовая работа по линейному программированию

Характеристика задач нечеткого математического программирования

К оглавлению…

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

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

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

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

Задачи математического программирования

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

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

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

Перечислим некоторые из таких постановок [8а].

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

Задача 2. Нечеткий вариант стандартной задачи математического программирования. Пусть определена следующая задача математического программирования:

Задачи математического программирования

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

Задача 3. Нечетко описана «максимизируемая » функция, т.е. задано отображение Задачи математического программирования, где Задачи математического программирования — универсальное множество альтернатив, Задачи математического программирования— числовая ось.

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

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

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

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

Задачи математического программирования

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

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

Задачи математического программирования

в которую цели и ограничения входят одинаковым образом.

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

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

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

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

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

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

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

Задачи математического программирования

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

Аналогично определяется функция принадлежности Задачи математического программирования для нечетких ограничений. В результате исходная задача оказывается сформулированной в форме задачи выполнения нечетко определенной цели, к которой применим подход Беллмана-Заде (8.2) [86].

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

Задачи математического программирования

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

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

Рассмотрим задачу нахождения минимума на заданной области. Пусть задана область вида:

Задачи математического программирования

где Задачи математического программирования — нечеткие подмножества множества Задачи математического программирования, а бинарная операция «+» обозначает сложение нечетких множеств.

Требуется найти

Задачи математического программирования

на заданной области.

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

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

Сведём решение исходной задачи к решению ряда задач линейного программирования. Для этого введём дискретные Задачи математического программирования-уровни [8в, 8г]. В результате нечёткие ограничения принимают следующий интервальный вид:

Задачи математического программирования

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

Задачи математического программирования

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

Задачи математического программирования

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

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

Задачи математического программирования

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

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

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