Линейное программирование: задачи с решением

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

Если что-то непонятно вы всегда можете написать мне в воцап и я вам помогу!

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

Возможно эта страница вам будет полезна:

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

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

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

Задача № 1

Фирма производит две модели и сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели требуется досок, а для изделия модели . Фирма может получить от своих поставщиков до 1700 досок в неделю. Для каждого изделия модели требуется 12 мин машинного времени, а для изделия модели — 30 мин. В неделю можно использовать 160 ч машинного времени.

Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели приносит 2 дол. прибыли, а каждое изделие модели — 4 дол. прибыли?

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

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

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

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

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

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

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

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

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

Штриховыми линиями на рис. 1.1 изображены прямые

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

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

Следовательно, максимальная прибыль составляет 2 X 300 + 4 X 200 = = 1400. При оптимальном решении оба ограничения превращаются в равенства, что означает полное использование сырья и машинного времени.

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

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

от вещественных переменных , удовлетворяющих условиям неотрицательности

и линейным ограничениям

Среди ограничений могут одновременно встречаться знаки и . Задача состоит в максимизации (минимизации) целевой функции.

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

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

максимизировать (минимизировать) функцию

Индекс 0 в векторе и в матрице указывает на то, что это начальные значения. Смысл этого станет ясен в разд. 1.3.

Возможно эта страница вам будет полезна:

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

Графическое решение двухмерных задач

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

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

Задача № 2

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

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

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

Минимальное значение функции = — 68 и достигается в точке =(12, 8). Заметим, что, как и в примере разд. 1.1, минимум достигается в вершине допустимой области. Оптимальным решением задачи является точка

минимальным значением функции = —68. Иногда задача имеет более чем одно оптимальное решение.

Задача № 3

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

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

На рис. 1.3 четырехугольник изображает допустимую область

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

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

Любая точка на отрезке представляется формулой

где

Для каждой такой точки значение функции равно

Функция имеет единственное минимальное значение. Иногда решение задачи не ограничено.

Задача № 4

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

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

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

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

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

Задача № 5

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

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

Ограничения задачи противоречивы, поэтому нет допустимых решений (рис. 1.5).

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

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

Возможно эта страница вам будет полезна:

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

Стандартная форма задач линейного программирования

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

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

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

а) Максимизация целевой функции

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

б) Ограничение в виде неравенств, например

может быть приведено к стандартной форме

где новая переменная неотрицательна.

Ограничение

может быть приведено к стандартной форме

где новая переменная неотрицательна.

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

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

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

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

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

Так, пример 1 разд 1.2 может быть приведен минимизировать функцию при ограничениях

Пример 1 разд 1.1 может быть приведен к следующему виду: минимизировать функцию

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

В матричной форме ограничения можно записать таким образом

Они состоят из двух уравнений с четырьмя неизвестными.

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

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

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

Из этих шести базисных решений только четыре допустимы и соответствуют вершинам допустимой области рис. 1.1 (см. приведенную таблицу).

В трехмерном случае линейные ограничения являются плоскостями,

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

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

Возможно эта страница вам будет полезна:

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

Обобщение на случай n переменных

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

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

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

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

Отрезок , где и — две точки, представленные векторами и , состоит из точек, определяемых соотношением

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

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

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

где

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

Возможно эта страница вам будет полезна:

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

Основные результаты линейного программирования

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

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

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

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

Ограничения можно задать в виде где матрица имеет ранг .

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

Утверждение 1. Если ограничения имеют допустимое решение, то они имеют и базисное решение.

Докажем это, построив базисное допустимое решение. Пусть в допустимом решении переменных равны 0, а остальные положительны. Тогда без потери общности

а — столбцы матрицы .

Если — линейно независимы, то — ранг матрицы и решение является базисным допустимым решением ( базисных переменных равны 0).

Если

линейно зависимы, то

где не все равны 0 или отрицательны (при необходимости это неравенство может быть умножено на —1). Пусть

тогда

Если выбрать так, что

то значения

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

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

Следовательно,

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

Утверждение 3. Базисные допустимые решения соответствуют вершинам выпуклого множества

Пусть

базисное допустимое решение.

Тогда является единственным решением уравнения , где , причем последние координат вектора равны 0.

Если — не вершина, то можно найти две другие точки и , такие, что

для некоторого , причем 0 < < 1 и выполнены условия

Таким образом, для последних координат имеем

Но поскольку

система равенств

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

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

что противоречит выбору . Поэтому каждое базисное допустимое решение — вершина.

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

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

положительны. Пусть

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

Как и при доказательстве утверждения 1, найдем такие не все равные 0, что

Легко видеть, что если

то векторы

удовлетворяют условию

Поскольку

то

Аналогично

Таким образом, — допустимые решения и

Следовательно, — не вершина, а это противоречит выбору , значит, не превосходит .

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

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

Если

Для любой другой точки в допустимой области

значение функции в этой точке

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

и минимизирующих функцию .

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

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

Итак, минимум функции достигается в вершине .

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

Возможно эта страница вам будет полезна:

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

Симплекс-метод при заданном начальном допустимом базисном решении

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

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

минимизировать

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

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

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

Если умножить ограничения системы (2.4) на , то исключатся из и мы получим

где

Разумеется, уравнения (2.4) и (2.3) выражают одинаковые ограничения, а уравнения (2.5) и (2.1) представляют одну и ту же целевую функцию, хотя и в разных алгебраических формах. Уравнения (2.4) и (2.5) являются канонической формой для базиса .

Если положить

равными 0, то соотношения

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

Отметим, что если матрица может быть разбита следующим образом:

где — матрица с коэффициентом на диагонали, a — матрица размерностью (остаток матрицы ), умножение уравнения (2.3) на приводит к уравнению (2.4). Для базисного допустимого решения должна существовать матрица .

Для системы уравнений (2.3) из соотношения

следует соотношение

т. е.

(это — уравнение (2.4)),

так что

для всех столбцов .

Имеем также

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

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

Задача № 6

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

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

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

Поскольку в этом случае коэффициенты положительны, а новые переменные имеют коэффициент +1, ясно, что набор , = 1700, = 1600 образует базисное фундаментальное решение, а уравнения (2.11) имеют соответствующий вид.

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

Однако при увеличении значения и будут изменяться, поскольку должны выполняться уравнения (2.11). Все переменные при этом должны оставаться неотрицательными. Таким образом, должен существовать предел увеличения .

Поскольку

обращается в 0 при = 1700/4 = =425.

Поскольку

обращается в 0 при = 1600/5 = 320.

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

Второе ограничение может быть записано в виде

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

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

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

Для уравнения

обращается в ноль при

Для уравнения

обращается в 0 при

Таким образом нельзя увеличивать более чем до 300 (минимального из этих значений). После деления на 7/5 (коэффициент при ) первое ограничение принимает вид

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

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

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

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

Ниже приведены три таблицы.

На итерации 0 звездочкой отмечено значение 5 — коэффициент при переменной, которую мы собираемся обратить в базисную в предельном ограничении. На итерации 1 отмечено число 7/5. Заметим также, что мы ставим точки вместо переменных, обязанных иметь нулевые значения, чтобы отличить их от переменных, обращающихся в 0 случайно.

Результаты, полученные в рассмотренном примере, можно обобщить. Предположим, что начальная каноническая форма задана и что на -й итерации получена каноническая форма, заданная уравнениями (2.4) и (2.5), запись которых приведена ниже в таблице.

Итерационный процесс состоит из трех шагов.

1 .Найти переменную для включения в базис.

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

  • Найти переменную для исключения из базиса.

Насколько можно увеличивать , не нарушая условия неотрицательности текущих базисных переменных? Если в -м ограничении > О, то наибольшее значение, которое может принимать переменная , равно иначе переменная . станет отрицательна. (Если < 0, то при увеличении базисная переменная будет возрастать.) Таким образом может увеличиваться до значения

Если этот минимум достигается в строке , то обращается в О, когда принимает значение . Другие базисные переменные останутся неотрицательными. Элемент называется ведущим элементом, строка — ведущей строкой, а столбец — ведущим столбцом.

  • Построить новую каноническую форму.

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

Затем удалим xs из других ограничений целевой функции. Для этого из -й строки c коэффициентом при вычтем X (новая ведущая строка). Чтобы преобразовать целевую функцию с коэффициентом (< 0) при , вычтем X (новая ведущая строка) из строки, соответствующей целевой функции.

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

где

Формулы (2.15) — (2.20) запоминать не надо; они приведены здесь для дальнейших ссылок. Вычисления удобнее выполнять в соответствии с шагом 3.

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

Задача № 7

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

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

Это — пример 2 разд.1.2, представленный в стандартной форме.

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

На итерации 1 коэффициенты при небазисных переменных неотрицательны. Сравнение с рис. 1.3 показывает, что мы передвинулись из точки 0 в точку . Оптимум найден в точке , в которой

с минимальным значением функции , равным —12.

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

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

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

Задача № 8

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

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

Ясно, что точка

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

Эта задача — пример 3 разд. 1.2. Приведем первую таблицу, соответствующую точке на рис. 1.4:

Здесь приведена также вторая таблица, вычисленная обычным образом. Она соответствует точке В на рис. 1.4. Функция z может быть еще уменьшена увеличением . Но здесь возникает определенная трудность. В столбце, соответствующем , в ограничениях нет строго положительных коэффициентов. Таким образом, сколько не увеличивай , базисная переменная никогда не обратится в 0. Действительно, будет увеличиваться, а — оставаться неизменным. Это случай неограниченного решения (см. рис. 1.4). В симплекс-метоце неограниченность решения выражается в том, что все коэффициенты < 0.

Возможно эта страница вам будет полезна:

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

Реализация симплекс-метода на эвм

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

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

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

Итерационная процедура состоит в основном из трех шагов. Сначала находим

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

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

Текст программы соответствует блок-схеме, приведенной на рис. 2.1; в программе используются те же обозначения, что и в тексте. Значения переменных и целевой функции запоминаются в нулевом столбце матрицы . Последняя строка этой матрицы используется для коэффициентов целевой функции. Данные в строках 4000 — 4030 соответствуют данным примера 1 разд. 2.1.

Полезно сделать следующие замечания по поводу этой программы. Минимум определяется в строках от 500 до 550 в предположении, что они существуют. Положив сначала переменную , можно избежать поиска ложного отрицательного значения. Следует помнить, что ЭВМ выполняет действия с конечной точностью. Симплекс-метод иногда требует длинных и скрупулезных вычислений, в процессе которых ошибки могут накапливаться; в частности, величины, которые должны быть нулевыми, могут принимать значения, скажем, —1,23947 X . Мы хотим избежать таких ошибочных отрицательных значений.

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

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

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

Процедура, начинающаяся со строки 9000, является форматирующей. Ее значение объясняется в приложении. Форматирующие значения РВ = 144 в строке 2020 и РВ = 122 в строке 3030, конечно, могут меняться в зависимости от значений, рассматриваемых величин и от требований точности при выводе.

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

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

Возможно эта страница вам будет полезна:

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

Порождение начального базисного допустимого решения

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

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

Пусть требуется решить следующую задачу.

Задача № 9

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

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

Это — пример 1 из разд.1.2; он решается графически без всяких затруднений. В стандартной форме с неотрицательными дополнительными переменными ограничениями принимают вид

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

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

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

и для них базисное решение очевидно. Это решение 0 (небазисные переменные),

Затем симплекс-метод используется для минимизации функции

функция называется искусственной целевой функцией. Этап I задачи состоит в минимизации функции .

Предположим, что ограничения (2.22) имеют допустимое решение и, следовательно, базисное допустимое решение (это не всегда так) ; тогда решение этапа I задачи закончится тем, что функция обратится в О и при этом и тоже будут нулевыми. Но когда и равны нулю, измененные ограничения (2.23) равносильны исходным (2.22). Базисное допустимое решение, минимизирующее функцию , может быть использовано как начальное базисное допустимое решение для минимизации функции на этапе II задачи. Начиная с этого момента нулевые значения и игнорируются.

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

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

На этой стадии минимизирована функция и>, переменные и небазисные и потому равны 0. Заметим, что можно было бы пренебречь еще на итерации 1 и уж точно с настоящего момента можно пренебречь и , и . Переменная сохранена просто для того, чтобы показать, что в оптимальное решение для функции и , и входят с коэффициентом 1, когда значение функции равно 0 . Поскольку выражение для функции , приведенной к данному базису, сохраняется, можно минимизировать функцию по-настоящему. Сейчас мы находимся в точке (рис. 1.2). Этап I задачи завершен, и конечная таблица без последних двух столбцов и без последней строки является входной для этапа II. Таблицы этапа II имеют следующий вид:

Последовательные таблицы 2, 3, 4 соответствуют точкам

(рис. 1.2). Последняя таблица оптимальна, так что минимум функции равен —68 при

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

Задача № 10

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

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

Приведем ограничения к стандартной форме

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

Симплекс-таблицы выглядят следующим образом:

На этой стадии функция минимизирована. Все коэффициенты в строке таблицы положительны. Но функция w не обратилась в 0, а = 5. Мы не можем найти допустимое решение неизмененных ограничений (2.26), что иллюстрирует и рис. 1.5. Этап I задачи завершен, но мы не можем перейти к этапу II, поскольку исходные ограничения не имеют допустимого базисного решения.

Задача № 11

Фирме требуется уголь с содержанием фосфора не более 0,03 % и с примесью пепла не более 3,25 %. Доступны три сорта угля по следующим ценам (за 1 т) :

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

Пусть 1 т смеси содержит угля типа соответственно.

Тогда

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

При этих ограничениях необходимо, чтобы значение функции было минимально.

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

Для неотрицательных

минимизировать

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

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

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

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

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

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

Этап I задачи заканчивается после итерации 1; затем значения и игнорируются. Минимальное значение функции равно дол.; оно достигается при

Возможно эта страница вам будет полезна:

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

Полное изложение симплекс-метода

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

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

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

минимизировать

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

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

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

с коэффициентом +1. Искусственные переменные

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

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

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

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

имеем следующие ограничения:

и функцию

которую необходимо минимизировать. Заполним первую таблицу.

Для вычислений можно использовать предыдущую программу (строки с 500-й по 1180-ую). Необходимо знать,на каком этапе задачи (I или II) в настоящий момент производятся вычисления. На этапе I = 1 (в программе); целевая функция хранится в строке , а с выражением для функции следует обращаться так же, как со всеми остальными ограничениями. На этапе II полагаем = 0; целевая функция z хранится в строке , а столбцы с искусственными переменными игнорируются. Когда в конце этапа I задачи минимизирована функция ; необходимо проверить, достигло ли ее значение 0 с точностью до ошибок округления, и приравнять 0, прежде чем переходить к этапу II задачи. Ниже приведена распечатка текста программы.

Если учесть все замечания, а также комментарии в тексте программы, то будет понятно, каким способом программа вводит дополнительные и искусственные переменные (строки с 100-й по 230-ую) и при необходимости — искусственную целевую функцию (строки с 250-й по 290-ю).

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

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

В конечной распечатке результатов (строки с 2000-й по 2300-ю) выводятся значения базисных переменных и признаки того, удовлетворяются ли ограничения как строгие неравенства или (связывающие) равенства. Это может быть полезно с точки зрения практической интерпретации, так как позволяет судить о том, какие из ресурсов исчерпаны. Снова используется форматирующая процедура 9000 (см. приложение). Форматные переменные в строках 2020 — 3030 могут быть изменены. При работе с большим количеством переменных оператор печати в строке 3000 следует изменить. Ее, конечно, можно подавить, скажем присвоив значение —1 первой величине из области данных.

Задача № 12

Найти такие неотрицательные

что

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

В этом примере

Соответствующие данные содержатся в строках 4000—4030. В распечатке приводятся вычисленные ранее таблицы:

Проблемы вырождения

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

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

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

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

Задача № 13

Найти

такие неотрицательные что

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

Графическое решение (рис. 2.2) показывает, что точка минимума —это точка (3,2), где = —7. Вырожденность возникает, поскольку прямые соответствующие ограничениям, пересекаются в одной точке (2, 0). Обычно вершина является пересечением всего двух прямых (в двухмерном случае). В данном примере в вершине пересекаются три прямые.

При использовании симплекс-метода первая таблица имеет следующий вид:

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

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

Итак, минимум функции равен -7 и достигается при

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

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

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

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

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

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

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

Задача № 14

Этот пример иллюстрирует зацикливание. Он был построен И. М. Л. Билом.

Найти такие неотрицательные

что

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

При решении этой задачи на ЭВМ случайно произошло зацикливание. Это свидетельствует о том, что для создания достаточно мощной программы необходимы некоторые изменения. На итерации производится выбор переменной для превращения ее в небазисную переменную (это может быть или ). Была выбрана переменная . На итерации 2 была выбрана переменная , а не . На итерации 4 была выбрана переменная , а не . Таблица на итерации 6 совпадает с начальной таблицей. ЭВМ будет продолжать вычисления, не уменьшая значения Функции . При вычислении вручную можно выбрать другие переменные. Читателю предлагается сделать это.

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

Минимум для функции достигается при

стальных

Минимальное значение функции

Возможно эта страница вам будет полезна:

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

Анализ устойчивости решения. Обращение базиса и симплекс-множители

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

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

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

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

на матрицу . Тогда получим соотношение

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

Симплекс-метод не состоит в непосредственном вычислении обратной матрицы. Этот метод — итеративный; по существу, он обращает базис, и это обращение может быть найдено из таблиц вычислений симплекс-методом.

Если — столбец из коэффициентов при переменной в первом ограничении в форме неравенства, то

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

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

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

В качестве иллюстрации рассмотрим первую и последнюю таблицы примера 1 разд.2.1.

Это — первая таблица.

А это — конечная оптимальная таблица.

Оптимальный базис — . Матрица коэффициентов этого базиса для ограничений на итерации 0 имеет вид

В первой канонической форме матрицы коэффициентов при

В конечной таблице она принимает

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

Таким же образом рассмотрим первую и последнюю таблицы примера 1 разд.2.3. Дополнительным переменным

соответствует Матрица из коэффициентов первой таблицы, т. е.

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

В окончательной таблице дополнительным переменным

соответствует матрица

поэтому (обратите внимание на изменение в первых двух столбцах) матрица представляет собой матрицу

что легко проверяется.

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

что также можно проверить.

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

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

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

Можно умножить ограничения на прибавить к выражению для функции и получить соотношение

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

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

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

Рассмотрим снова таблицу примера 1 разд.2.1. Коэффициенты при и в оптимальном виде для функции равны соответственно 2/7 и 4/7; это и есть симплекс-множители для оптимального базиса.

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

Умножим ограничения (как показано выше) на и и прибавив их к функции

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

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

Для только что рассмотренного примера это очевидно (см. уравнение (3.10)).

Для примера 2 разд 2.3 коэффициенты при

в конечной таблице равны (0, 0, 16/5, 1/5), а симплекс-множители равны (-0, -0, 16/5, 1/5) (заметим, что в первых двух случаях поменялся знак; в рассматриваемом случае это не имеет значения).

Проверьте, что умножение ограничений в виде равенств (2.22) на (0, 0, 16/5, 1/5) с последующим прибавлением к выражению для функции , как указано в (2.22), действительно приводит к канонической форме для функции и что -(-О X 10 + -0 X 5 + 16/5 X 20 + 1/5 X 20) = = -68.

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

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

Возможно эта страница вам будет полезна:

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

Что получается при изменении задачи

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

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

Давайте последовательно рассмотрим:

1) изменения в (значения правых частей);

2) изменения в (коэффициенты целевой функции);

3) включение дополнительных переменных;

4) включение дополнительных ограничений. 1) Изменения в

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

с той же целевой функцией .

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

Из уравнения (3.7) значение целевой функции выражается следующим образом:

причем все

(коэффициенты при базисных переменных равны 0, при небазисных переменных 0).

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

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

Таким образом из уравнения (3.13) можно получить

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

Задача № 15

Рассмотрим еще раз пример 1 разд. 1.1. (Для удобства повторим задачу.)

Фирма производит две модели и сборных книжных полок. Их производство ограничено наличием сырья высококачественных досок и временем машинной обработки. Для каждого изделия модели требуется 3 досок, а для изделия модели . Фирма может получить от своих поставщиков до 1700 досок в неделю. На каждое изделие модели требуется 12 мин машинного времени, а на изделие модели — 30 мин. В неделю можно использовать 160 ч машинного времени. Если каждое изделие модели приносит 2 дол. прибыли, а изделие модели — 4 дол. прибыли, сколько изделий каждой модели фирме необходимо выпускать в неделю?

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

при которых минимизируется функция

(прибыль, взятая с обратным знаком).

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

Обращенный базис имеет вид

симплекс-множители равны 2/7, 4/7.

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

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

Новыми значениями базисных переменных будут

что допустимо.

Оптимальное значение для функции меняется на , в данном случае

Таким образом, прибыль возрастает на 2/7 дол., и это — максимальная цена, которую следует заплатить за дополнительный 1 доски. Нет смысла приобретать дополнительное сырье. Максимальная цена равна

2. Предположим, что имеется возможность получения дополнительного машинного времени. Выгодно ли это, если 1 ч машинного времени стоит 7 дол.?

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

что недопустимо.

Оптимальное значение для функции заменяется на значение —

Прибыль увеличивается на 40/7 дол. Поскольку дополнительный 1 ч машинного времени стоит 7 дол., это невыгодно.

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

Заметьте, что в пункте новое значение для функции z равно —2(300 + + 5/7) — 4(200 — 2/7), а в пункте — равно -2(300 — 40/7) — 4(200 + + 30/7).

2) Изменения в

Задача № 16

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

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

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

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

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

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

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

3) Включение дополнительных переменных

Задача № 17

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

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

что

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

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

Поскольку симплекс-множители из уравнения (3.7) следует, что коэффициент при в канонической форме для функции

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

Если

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

Если

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

4) Включение дополнительных ограничений

Задача № 18

Предположим, что в период экономического кризиса торговые агенты сообщают, что рынок принимает не более 550 полок в неделю. Как это отразится на производстве? Указанное ограничение на объем продажи равносильно ограничению

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

так что

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

Если бы экономический кризис был серьезнее, с ограничением рынка

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

Двойственный симплекс-метод

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

Задача № 19

Предположим, что недельная продажа ограничена 450 полками. Тогда должно быть включено дополнительное ограничение

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

где — дополнительная переменная.

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

Поэтому уравнение

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

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

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

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

В нашей задаче базисная переменная отрицательна и является кандидатом на удаление из базиса. Какая переменная должна ее заменить? В строке таблицы ищется отрицательный ведущий элемент, такой, что при последующих преобразованиях (которые снова примут вид уравнений (2.15) — (2.20)) коэффициенты целевой функции будут оставаться положительными. Перед формализацией этих правил посмотрим, как они выполняются в нашей задаче. В строке имеется только один отрицательный коэффициент — коэффициент при , равный —3/7. Если мы разделим уравнение на —3/7, чтобы включить в базисные переменные переменную (с коэффициентом 1), то получим уравнение

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

В конечной таблице приведено оптимальное решение новой задачи:

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

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

  • Найти отрицательную базисную переменную. Если ее нет, то оптимальное решение найдено; если их более чем одна, надо взять из них самую отрицательную. Пусть эта переменная — базисная в -м ограничении. Она является переменной для исключения из базиса.
  • В -й строке найти отрицательный коэффициент . Если его нет, то, очевидно, не существует допустимого решения задачи. Для отрицательных коэффициентов в этой строке найти

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

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

и, поскольку все отрицательны, a положительны, эта величина положительна, так как s выведено из соотношения

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

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

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

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

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

Задача № 20

Найти такие неотрицательные

что

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

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

что

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

Если базисными переменными являются

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

Если умножить эти ограничения на —1 (для получения корректного вида базиса) будем иметь

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

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

Это можно проверить графически.

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

Возможно эта страница вам будет полезна:

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

Транспортная задача. Постановка задачи и ее решение

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

Задача № 21

Фирма должна отправить некоторое количество кроватей с трех складов в пять магазинов. На складах имеется соответственно 15, 25, 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 12 кроватей. Стоимость перевозки одной кровати (в долларах) со склада в магазин приведена в таблице.

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

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

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

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

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

и минимизирующих функцию

Короче, соотношения (4.2) можно переписать так:

найти такие , для которых справедливы неравенства

и которые минимизируют функцию

Поскольку

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

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

в виде равенств примера 1 и чтобы сумма произведений этих переменных на стоимости (указанные в правом нижнем углу каждой клетки) была минимальна. Приведенный на рисунке массив соответствует данным примера 1:

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

Представляя данные в таком виде, легко построить первое базисное допустимое решение задачи. Это можно сделать по правилу «самая дешевая продукция реализуется первой». Поскольку задача состоит в минимизации общей стоимости, находим наименьшую стоимость во всех клетках: 0 в строке 1, столбце 2 и присваиваем переменной значение 12 (наименьшая из сумм по строке и по столбцу). Теперь столбец 2 можно удалить, уменьшив сумму по строке на 12, т. е. заменив ее на 3. Потом та же процедура применяется к полученному массиву.

Затем переменной и присваивается значение 3 (или переменной — значение 5), удаляется строка 1, сумма по столбцу 1 заменяется на 17 и осуществляется переход к следующему массиву и т. д.

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

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

Полная стоимость, соответствующая этому решению, С — 3 X 1 + + 12X0 + 2X5 + 8X3 +15X3 +15 Х4 + 5Х 1=147 дол.

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

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

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

Такая система уравнений решается последовательными подстановками. «Треугольник коэффициентов» может содержать нулевые элементы, но диагональные коэффициенты должны быть отличны от 0.

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

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

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

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

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

Утверждение 2. Значения всех базисных переменных задаются соотношениями

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

Поэтому

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

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

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

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

Возможно эта страница вам будет полезна:

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

Алгоритм последовательного улучшения плана

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

Транспортную задачу можно решить и применением симплекс-метода, но в данном случае этот метод неэффективен, так как используются ограничения специального вида. Мы будем решать эту задачу с помощью алгоритма последовательного улучшения, разработанного Ф. Л. Хитчко-ком. Рассмотрим задачу из примера 1 разд. 4.1 (результаты можно обобщить, используя симплекс-множители, описанные в предыдущей главе).

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

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

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

Следовательно,

Уравнение (4.7) — это специальный вид уравнения (3.7) для транспортной задачи. Коэффициент при равен

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

Далее если уравнение (4.7) является канонической формой целевой функции, соответствующей базису, то коэффициенты при базисных переменных равны 0.

Таким образом, для занятых клеток массива справедливо соотношение

следовательно, можно определить и .

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

Имеется 8 неизвестных

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

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

Теперь можно проверить, оптимально ли это решение. Если — коэффициент при в канонической форме для целевой функции, то из уравнений (4.7) следует, что

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

Ясно, что для нашей задачи увеличение приведет к уменьшению целевой функции. Действительно, каждое увеличение на 1 уменьшит целевую функцию на 3. При увеличении значения на число необходимо уменьшить на число , чтобы сохранить сумму в строке (2). Для того чтобы сохранить значение суммы в столбце (1), необходимо увеличить на число , а затем для сохранения суммы в строке (1) уменьшить на число Заметим, что другой метод: положить = уменьшить на число до значения 8 — , поскольку невозможно сохранить сумму в столбце (4), не вводя дополнительных переменных, — приводит к некоторым трудностям и с его помощью невозможно получить базисное решение. Программа должна избегать таких «тупиковых путей».

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

Для этого массива

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

Значение стоимости уменьшается:

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

Минимальное значение стоимости равно 121 дол. Отметим, что значение стоимости задается уравнением

что непосредственно следует из уравнения (4.7) , так как в его левой части все слагаемые равны 0 (поскольку либо переменная базисная, а следовательно, коэффициент при ней равен нулю, либо переменная небазисная и, значит, равна 0). Заметим, что уравнение (4.10) — просто частный случай уравнения (3.11) для транспортной задачи.

Проверьте справедливость уравнения (4.10) для каждого из массивов. Такая проверка полезна на каждом шаге итерационной процедуры.

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

Возможно эта страница вам будет полезна:

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

Дисбаланс и вырожденность в транспортной задаче

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

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

Пусть 15, 25, 20 кроватей, хранящихся на складах , должны быть распределены по четырем магазинам, где требуется 20, 12, 5 и 9 кроватей. Пусть стоимость перевозки одной кровати со складов в магазины задается таблицей

Как следует планировать перевозку для минимизации стоимости?

Склады располагают 60 кроватями. Магазинам требуется лишь 46 кроватей. Для того чтобы перейти к транспортной задаче, введем фиктивный магазин, которому требуется 14 кроватей. Стоимость перевозок со склада в этот магазин полагается равной 0. Если в окончательном решении будет получено, что некоторые кровати надо будет отправить в этот магазин, то это будет проигнорировано. Кровати останутся на складе. Таким образом, поставлена транспортная задача, для которой уравнения (4.1) выполняются.

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

Переменная входит в базис; максимальное значение равно 5; переменная исключается из базиса:

14 кроватей из клетки (3, 5) остаются на складе 3. Потребности магазинов полностью удовлетворены. Мы получили оптимальное решение

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

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

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

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

Задача № 22

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

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

Заметим, что общее предложение (5000 пальто) превосходит общий спрос (3700 пальто). Поэтому введем фиктивный сорт пальто, количество которых составит 1300; задача превращается в транспортную. Стоимость одного пальто этого сорта будет нулевой, и спрос на эти пальто в окончательном решении будет игнорироваться. Он будет просто отражать избыточную производственную мощность. Решать задачу удобно, принимая за единицу 100 пальто.

Массив задачи принимает вид

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

Максимальное значение равно 2; оно обратит в 0 и , и (в очевидных обозначениях). Только одна из этих переменных, предположим , удаляется из базиса. Ниже приведено базисное допустимое решение с симплекс-множителями и , содержащее шесть базисных переменных, одна из которой равна 0:

Максимальное значение равно 3, и следующее решение не вырождено:

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

Следовательно, имеется два оптимальных решения, для которых стоимость = 410 900 дол.

Первое решение: фирма поставляет 1000 пальто размера и 200 пальто размера ; фирма поставляет 1300 пальто размера и 1200 пальто размера .

Второе решение: фирма поставляет 200 пальто размера , фирма — 1000 пальто размера , фирма — 1300 пальто размера и 1200 пальто размера .

Второе решение кажется более приемлемым, хотя такое распределение заказов тоже несправедливо, как и в первом решении.

Вырожденности можно избежать, слегка изменив суммы по строкам так, чтобы частичные суммы сумм по строкам не совпадали с частичными суммами сумм по столбцам. Можно положить суммы по строкам равными 10,01 ; 15,01; 25,01; по столбцам 10; 15 ; 12 и 13,03. В окончательном решении можно округлить дробные значения до целых. Проведите вычисления (ясно, что они аналогичны вышеописанным вычислениям).

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

Постановка транспортной задачи на эвм

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

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

Теперь приведем блок-схему определения первого допустимого базисного решения (строки 500-840) [рис. 4.18].

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

должны быть равны 0. Переменные

должны быть равны количеству переменных соответственно в 1-й строке и в -м столбце.

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

Процедура перехода к новому базисному допустимому решению (начиная со строки 2000 до строки 3250) заслуживает внимательного изучения. Поясним ее подробнее. Сначала находится «цепь» ± клеток, которая не является «тупиковым путем» (строки 2050-2730).

На шаге 1 мы находимся в клетке — счетчик шагов, — индикатор «тупикового пути»,

клетка, в которую мы попадаем на шаге . Массив состоит из ± 1, соответствующих ± ; положим = 1, если клетка используется,

если строки и столбцы входят в цикл.

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

в неотмеченной клетке (строка 2150). Если это единственная переменная в своем столбце, то производится присваивание = 1 (строка 2170). Разумеется, это не делается в начальном столбце . После того как подходящая переменная найдена в столбце , поиск прекращается; при этом = 1.

Затем увеличивается для следующего шага, в переменную заносится номер текущей строки, а в переменную — номер только что найденного столбца ; соответствующему присваивается значение — 1, и найденная клетка помечается присвоением значения 1 (строка 2320). Если мы снова оказались в столбце , откуда начали, то цикл завершен (строка 2400). В противном случае ищем столбец для строки, содержащей базисную переменную в неотмеченных строке и клетке; таким образом снова помечаются «тупиковые пути». Как только искомый столбец найден, поиск прекращается присвоением = 1. Затем увеличивается для следующего шага, переменной присваивается номер только что найденной строки , а — номер только что обрабатывавшегося столбца; для этой клетки осуществляются присвоения: = +1, = 1, после чего программа возвращается к поиску строки в строке 2100 программы.

Заметим, что если в процессе поиска строки не удается найти столбец ( = 0 в строке 2190), не являющийся «тупиковым путем», то происходит возвращение (строка 2210) к строке предыдущего поиска столбца. Если в поисках столбца удается найти только строки ( = 0 в строке 2590), соответствующие тупиковым путям, то осуществляется возвращение (строка 2610) к строке предыдущего поиска строки. Однако в силу того, что сохраняет свое значение, ошибка не повторяется в дальнейшем ( = 1 в строках 2150 и 2550). Поскольку базис задан треугольной системой уравнений, процесс в конце концов закончится и управление будет передано из строки 2400 в строку 3000.

В строках 3000 — 3040 программы содержится наименьшая базисная переменная из клеток, в которых = — 1. Здесь определяются значение w и положение переменной , которая будет удалена из базиса. В строках 3100 — 3120 клетки включаются в цепь. В конечном счете переменная определяется как базисная, переменная — как небазисная и определяется количество базисных переменных во всех строках и столбцах. Затем программа возвращается к вычислению симплекс-множителей и .

При работе программы печать ( и ) в строках 1340— 1342 и наибольшего по модулю значения в строке 1581, а также печать в строках 2071, 2321 и 2721 могут быть подавлены. Последние три строки отражают цепи и обратный поиск. Печать в строке 3221, определяющая w и переменную для удаления из базиса, тоже может быть подавлена.

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

Возможно эта страница вам будет полезна:

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

Задача о назначениях

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

Задача № 23

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

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

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

Таким образом, это задача линейного программирования транспортного типа. Поскольку все суммы по строкам и по столбцам равны 1, она вырождена, так что алгоритм решения транспортной задачи применим, но неэффективен. Поскольку задача транспортная, в ее оптимальном решении (целочисленном) пять из величин будут равны 1, а остальные -0. С другой стороны, в матрице времени размерностью 5X5 надо найти пять элементов — по одному в каждой строке и каждом столбце, таких, что сумма выбранных элементов минимальна. Условие равенства 0 или 1 в некоторых случаях необходимо, чтобы придать смысл формулировке задачи (см., например, первую фразу рассматриваемого примера). Это постулат.

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

где

некоторая перестановка элементов 1, 2, . . ., . Таких перестановок — !, так что даже при минимальном количестве решение полным перебором является недопустимо длинным.

Метод Мака для решения задачи о назначении

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

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

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

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

Метод Мака для задачи выбора

Основатель метода К. Мак очень хорошо описал его в [15]. Рассматривается задача выбора размерностью . Выберем по минимальному элементу в каждой строке. Подчеркнем каждый из этих минимальных элементов. Если в каждом столбце имеется ровно по одному подчеркнутому элементу, то подчеркнутые элементы — базис — определяют оптимальный выбор.

Начало

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

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

Шаг 2. Пусть элемент множества из строки равен а минимальный элемент множества из строки равен . Пусть

Шаг 3. Увеличить все элементы множества на . Шаг 4. Отметить точками внизу. Теперь — «отмеченный точками элемент».

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

Теперь можно подчеркнуть элементы в еще одном столбце. Шаг 6. Подчеркнуть последний элемент полностью. Это — новый подчеркнутый элемент.

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

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

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

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

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

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

Ниже приводится полное описание этого метода для решения примера 1 разд. 5.1.

Задача № 24

Ежедневно авиалиния, которая принадлежит некоторой компании, осуществляет следующие перелеты между городами и :

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

Напишите расписание полетов, совершаемых каждым из самолетов.

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

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

Так что последовательность в целом имеет следующий вид:

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

Реализация метода Мака на эвм

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

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

В строках 250—310 программы минимальным элементом строки I является из столбца . В строках 320-360 пусть — количество минимумов в столбце — значение минимума в 1-й строке, — строка -го минимума в столбце — столбец из строки I. Началу и шагу 1 соответствуют строки программы 400—470, где находится столбец с двумя и более минимумами; строки, в которых находятся эти минимумы, запоминаются в переменных и т. д. В строке 480 — количество столбцовое которых производились одновременные увеличения (в начале = 1); и т. д. -список номеров столбцов из множества , a для таких столбцов равна 1; — значение, на которое увеличены элементы столбца .

Шаг 2 — строки программы 520-640; — разность между элементом в строке ) столбца и минимумом в строке I. Столбцы множества , для которых = 1, исключаются. Наименьшее значение присваивается IV, и это — наименьшее значение, нужное для соответствия одному из минимумов по строкам в множестве — столбец соответствующего элемента, a — номер его строки, — общее значение, на которое увеличиваются элементы в столбце (строки 650-670). В данный момент на IV увеличиваются только значения минимумов в строке . Это — модифицированный шаг 3 (680—700) .

В строке 720 столбец добавляется к множеству , т. е. полагаются равными . В строке 750 указывает строку минимума в столбце — столбец минимума в строке . Строка 770: в столбце имеется минимумов. Если в столбце нет минимумов, минимумы в строке располагаются так, чтобы покрыть один лишний столбец (переход от строки 780 к строке 840). В противном случае эти минимумы прибавляются к минимумам из предыдущих столбцов, соответственно увеличивается, а строки минимумов из запоминаются в . Это — шаг 5, и в строке программы 520 происходит возвращение к шагу 2.

Если после шага 5 осуществляется переход к строке 840, то необходимо переместить минимум (шаг 6). В строке 850 программы представляет собой столбец с номером матрицы . Вновь обнуляем , т. е. исключаем его из множества . Элемент является тем значением, на которое был номинально увеличен столбец . Теперь все элементы столбца фактически увеличены на это значение (строка 880 программы).

В строке 910 программы находится один минимум в столбце . Новый минимум находится в строке столбца (шаг 6); в строке 930 — столбец предыдущего минимума в строке , так что в строке 940 полагаем . Количество минимумов в этом столбце , где равно исходному значению . В строках 970-1020 программы определяется, какой из минимумов столбца находится в строке . Он исключается или заменяется. В строке 1030 программы происходит следующее: если в столбце находится более одного минимума, перераспределение минимумов закончено, приравнивается 1, управление возвращается к строке 400 (старт) для нахождения столбцов с более чем одним минимумом. Если программа дойдет до строки 1040, то в столбце будет найден всего один минимум; — номер его строки, так что новое значение (строка одного минимума в столбце ) и есть новое значение . Таким образом, процесс повторяется с новым столбцом в строке 930 программы.

В строку 1500 управление передается из строки 420, где обнаруживается отсутствие столбцов с более чем одним минимумом. Теперь минимумы в строках распределены по столбцам, и оптимальный выбор найден. Строка первого (и единственного) минимума в столбце J есть 1С (см. строку 1520), так что оптимальные выборы извлекаются из элементов строки I столбца JV(I) (см. строку 1550). Они распечатываются, и оптимальная сумма заносится в Т.

Задача № 25

Для матрицы

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

Улучшенный симплекс-метод алгоритм

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

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

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

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

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

найти такие

что

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

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

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

Уравнения (6.3) — каноническая форма, соответствующая базисным переменным

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

Улучшенный симплекс-метод — это итерационная процедура, основанная на том, что на -й итерации известны:

базисные переменные и их значения;

обращение базиса;

соответствующие базису симплекс-множители.

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

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

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

В уравнении (6.4) числа — текущие симплекс-множители, а коэффициенты — исходные коэффициенты из уравнения (6.3) .

Величины вычисляются для каждой небазисной переменной. Для базисных переменных они, разумеется, обращаются в 0. Затем, следуя симплекс-методу, находим . Если , то на следующей итерации переменная войдет в базис. Если ,то минимум функции найден.

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

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

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

  • Теперь можно вычислить новый базис, его обращение и симплекс-множители.

а) Старый базис заменяется на новый .

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

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

Следовательно,

(См. упр. 15 гл. 3).

Таким образом, если

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

столбца и в качестве ведущего элемента.

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

так как в базис теперь вместо входит . Значит,

поскольку слагаемое при равно 0. Следовательно,

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

Итак,

(см. также уравнение (2.10) и разд. 3.2). Следовательно,

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

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

Задача № 26

Найти неотрицательные удовлетворяющие условиям

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

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

Эти данные сохраняются в течение всех вычислений. Если задача решается с помощью ЭВМ, они должны быть записаны в память ЭВМ.

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

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

На итерации 4 получаем оптимальное решение, в котором

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

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

Легко проверить, что симплекс-множители оптимальному базису, суть

Следует отметить, что вычисления производились в матрице размерностью 4X4 (состоящей из значений переменных, обработанных элементов и симплекс-множителей). При использовании симплекс-метода вычисления производились бы в матрице значений и коэффициентов размерностью 4X7.

Возможно эта страница вам будет полезна:

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

Инициализация алгоритма

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

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

от для функции , добавленных к симплекс-множителям

для функции — настоящей целевой функции.

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

В соответствии с уравнением (6.4) получаем

где исходные коэффициенты равны 0 для всех коэффициентов , кроме искусственных. Для искусственных переменных коэффициенты равны 1, поскольку — сумма этих переменных.

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

Величины как и прежде, равны 0. В фазе I вычислений величины и преобразуются в соответствии с уравнением (6.16), использующим для и для . Величины и вычисляются из уравнений (6 4) и (6.17) соответственно. Следовательно, как только этап I завершится, а функция обратится в 0 (если этого не произойдет, ограничения не имеют допустимого решения), можно продолжить минимизацию функции без особых затруднений.

Задача № 27

Найти такие

что

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

Задача в стандартной форме с новыми и искусственными переменны

ми имеет вид

На итерации 2 обращается в 0. Если воспользоваться уравнением (6.4) и подходящими симплекс-множителями для функции (-5/9, -25/9, 0), то ясно, что функция оптимизируется также и этим базисным допустимым решением, в которому , и минимальное значение функции равно 30. Поскольку третье ограничение превращается в строгое неравенство.

Еще раз о вырожденности

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

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

Итак, вместо следующей задачи:

найти , удовлетворяющие соотношению

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

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

найти , удовлетворяющие соотношению

и минимизирующие функцию

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

На -1 итерации получим, например, базис и его обращение, матрицу с элементами Тогда из уравнения (2.8) ясно, что значения базисных переменных возмущенной задачи имеют вид

где — значения исходной задачи.

Разумеется, выбор произволен лишь потому, что базис остается допустимым. Если > 0, то в силу ограниченности элементов можно быть уверенными, что при достаточно малом . Если = 0, то мы должны быть уверены в том, что первое ненулевое положительно, так как > 0.

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

для

Теперь вырожденность исходной задачи означает, что здесь может встретиться неоднозначность минимизации

для

Если минимум для единствен и равен , то при достаточно малом минимум (6.21) будет достигаться для одного и того же значения .

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

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

Если в (6.22) возникают неопределенности, следует в (6.21) рассмотреть члены первого порядка по . Таким образом ищется минимум

среди значений , связанных с неопределенностью (6.22) Итак, находится из соотношения

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

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

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

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

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

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

Новое значение функции

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

Задача № 28

Найти неотрицательные удовлетворяющие условиям

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

Оптимум для функции равен -7 при

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

Поскольку мало, ясно, что это второе отношение. Неопределенность в «значениях» разрешается в первом столбце обращения:

Программа для улучшенного симплекс-метода

Представленная ниже программа реализует идеи настоящей главы. Она похожа на программу гл. 2. Исходная матрица коэффициентов заносится в память как матрица , правые части ограничений заносятся в столбец 0. Таким образом, в матрицу входят + 2 строк, ограничений, целевая функция и искусственная целевая функция. Она имеет строк помимо строки 0, которые содержат исходные, новые и искусственные переменные. Матрица состоит из столбцов значений переменных и значений целевой функции, матрицы обращения размерностью , двух строк симплекс-множителей и последнего столбца, в котором все элементы, кроме последних двух, равны 0, а последние два равны — 1:

Матрицам и присваиваются значения в строке 60 и строках 100—500.

Величины из уравнения (6.4) или из уравнения (6.17) вычисляются в строках 530 и 540. В силу указанного выше вида матрицы , вычисляются в строках 760—780 и запоминаются как . Правила предыдущего раздела для разрешения неопределенности реализуются в строках программы 790—1000. Рекомендуем внимательно сравнить этот раздел программы со строками 740-810 программы разд. 2.4.

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

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

Большим преимуществом улучшенного симплекстметода является уменьшение количества вычислений. Симплекс-метод работает с матрицей , имеющей + 2 строки и столбцов. Улучшенный симплекс-метод работает с матрицей , имеющей + 2 строк и + 1 столбцов. Таким образом, количество вычислений в задаче линейного программирования напрямую связано скорее с количеством ограничений, чем с количеством переменных, которое в общем случае значительно больше.

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

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

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

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

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

найти такие

что

и функция имеет максимальное значение.

Ей соответствует двойственная задача: найти такие

что

и функция имеет минимальное значение.

На самом деле нам уже встречались прямая и двойственная задачи в упр. 5, 6 гл. 2 и в упр. 3, 4 гл. 6, Исходная задача: найти такие

что

и функция

имеет минимальное значение.

Соответствующая двойственная задача: найти такие

что

и функция

имеет максимальное значение.

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

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

и функция

имеет минимальное значение.

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

найти такой , что

и функция

имеет максимальное значение.

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

Задача № 29

Привести к стандартной форме прямую задачу найти такие

что

и функция

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

Максимизация функции равносильна минимизации, например, функции .

Ограничение умножением на -1 преобразуется в ограничение — .

Ограничение

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

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

что

и функция

имеет минимальное Это — стандартная форма прямой задачи. Двойственная задача имеет следующий вид: найти такие

(смысл этих обозначений скоро станет ясен), что

и функция

имеет максимальное значение.

Это стандартная двойственная задача. Видно, что

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

и функция

имеет максимальное значение.

Задача № 30

Найти двойственную задачу для задачи найти такие неопределенного знака, что

и функция имеет минимальное значение.

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

и функция

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

и функция имеет максимальное значение.

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

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

найти такие что

и функция

имеет максимальное значение.

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

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

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

Теорема 1. Двойственная задача к двойственной есть прямая задача.

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

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

найти такой , что

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

и функция имеет минимальное значение, а это и есть прямая задача.

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

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

Из уравнения (7.3) Поскольку , то

Далее из уравнения (7.4) , и поскольку , то

Однако — скалярная величина, поэтому равна своей транспозиции следовательно,

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

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

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

найти такие

и функция

имеет минимальное значение.

Если

симплекс-множители оптимального решения, то после умножения ограничений на

и прибавления к выражению для функции получаем уравнение

Далее если уравнение (7.6) — оптимальная каноническая форма для функции , то все коэффициенты левой части неотрицательны. Следовательно,

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

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

Разумеется, в уравнении (7.6) коэффициенты при базисных переменных обратятся в 0; сами базисные переменные также равны 0, так что левая часть равна 0 и

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

Но это — значение функции , соответствующее допустимому решению ограничений двойственной задачи, задаваемому равенствами .

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

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

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

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

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

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

где

— вектор новых переменных.

Если

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

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

что можно записать в виде

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

Следствием теорем 3 и 4 является то, что при встрече с задачей линейного программирования мы вольны выбирать, решать ли задачу в том виде, как она поставлена, или решать двойственную задачу. Если применяется улучшенный симплекс-метод (что настоятельно рекомендуется), то будут подучены и- значения переменных, и симплекс-множители. Это позволит определить также симплекс-множители и значения переменных другой задачи. Таким образом можно сильно сэкономить время вычислений. Как было указано в разд. 6.4, объем вычислений в задаче линейного программирования связан скорее с количеством ограничений, чем с количеством переменных.

Значит, если в прямую задачу входят 7 ограничений на 3 переменные, преобразования будут производиться в матрице размерностью 9 X 8 на этапе I и в матрице размерностью 8 X 8 на этапе II. В двойственную задачу входят 3 ограничения на 7 переменных, и она независима от этапа I; преобразования будут производиться в матрице размерностью 4X4. Таким образом, из каждой итерации объем вычислений сокращается по меньшей мере в четыре раза.

В качестве иллюстраций к теоремам 3 и 4 рассмотрим задачу найти такие

что

и функция

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

что

и функция

имеет максимальное значение.

Решение первой задачи на ЭВМ показывает, что в оптимальном решении

(из нижней строки) и = 47. Таким образом, для другой задачи решением является

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

(знаки целевой функции и симплекс-множителей здесь обращены).

Уместно еще одно замечание. Из уравнения (7.6) видно, что в оптимальном решении прямой задачи

Из уравнения (7.11) видно, что в оптимальном решении двойственной задачи

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

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

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

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

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

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

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

найти такие

и функция

имеет минимальное значение.

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

Таким образом, в оптимальном решении

Симплекс-множители (коэффициенты при новых переменных и в окончательном виде для функции ) равны

Рассмотрим двойственную задачу

найти такие

и функция

имеет максимальное значение.

При обычном подходе к задаче мы минимизируем функцию

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

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

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

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

принимает минимальные значения (см. уравнение (4.2)).

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

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

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

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

(см. уравнение (4.7) ).

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

Когда для небазисных переменных

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

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

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

Обычно , но здесь, пренебрегая этим, имеет смысл сформулировать задачу в общем виде. Запишем ограничения (7.18) и (7.19) в виде

и определим функцию Лагранжа

где и — так называемые множители Лагранжа.

Условный минимум, определенный уравнением (7.17), задается безусловным минимумом, определенным уравнением (7.22), необходимые условия которого задаются уравнениями

следовательно,

Видно, что уравнения (7.24) и (7.25) равносильны уравнениям (7.18) и (7.19). Уравнения (7.26) и (7.27) отражают свойство комплементарности дополнительных переменных. Множители Лагранжа , эквивалентны симплекс-множителям.

Значения переменных удовлетворяют ограничениям

Далее из уравнения (7.22) получаем уравнения

Сравните их с уравнением (3.17).

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

Сравните с уравнениями (7.7). Таким образом, из уравнения (7.23) имеем

следовательно

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

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

в силу уравнений (7.27) при Для этих значений

т. e. в обозначениях прямой и двойственной задач.

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