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

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

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

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

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

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

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

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

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

Задача № 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. в обозначениях прямой и двойственной задач.

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

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

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

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

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

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

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

При этом на переменные наложены линейные ограничения:

Здесь коэффициенты — заданные числа, а величины — неизвестные. Каждое из ограничений системы — одно из трех возможных: .

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

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

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

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

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

• Пример №1. Задача распределения ресурсов.
• Пример №2. Задача о раскрое.
• Пример №3. Задача о смеси.
• Пример №4. Задача планирования производства.
• Пример №5. Транспортная задача.
• Пример №6. Минимизация дисбаланса на линии сборки.

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

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

где

данные числа.

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

Каждое такое неравенство определяет полуплоскость, лежащую по одну сторону прямой

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

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

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

Пример задачи с решением:

• Пример №7. Построить допустимую область системы неравенств

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

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

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

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

Пример задачи с решением:

• Пример №10. Решить графически следующую ЗЛП

Понятие об анализе на чувствительность

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

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

Пример задачи с решением:

• Пример №12. Фирма производит два вида продукции

Первая задача анализа на чувствительность

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

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

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

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

Если, например, увеличить правую часть ограничения , сделать ее больше нуля, прямая переместится вниз. Но до тех пор, пока точка пересечения прямой с прямой лежит выше точки по-прежнему достигается во всех точках отрезка и равен 1000. В частности, точка (35; 7,5) будет одним из оптимальных решений задачи. Последний раз это произойдет, когда точки и сольются. Подставляя в уравнение координаты точки , получаем, что

Как только а превзойдет число 9,5, оптимальной станет точка пересечения отрезка и прямой

В этом случае всегда нужно производить 35 единиц продукции . Количество единиц продукции определяется из уравнения

Значит, если , система ограничений становится несовместной.

Отметим, что неравенство

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

и трактовать следующим образом: объем сбыта продукции составляет не менее 60% всего объема реализованной продукции плюс дополнительно а единиц.

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

Тогда прямая начнет перемещаться вверх (рис. 2.9).

При перемещении вверх прямой отрезок , в конце концов, стянется в точку (35; 70/3). Уравнение прямой :

В точке , лежащей на пересечении прямых

становятся связывающими оба ограничения:

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

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

Вторая задача анализа на чувствительность

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

У нас всего одно связывающее ограничение. Мы показали, что целевую функцию можно увеличить на 1900/3 единицы, если увеличить запасы сырья на 190/3 единицы.

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

где — номер соответствующего ограничения.

В нашем примере ценность единственного ресурса равна

Другими словами, увеличение на единицу объема ресурса приведет к росту целевой функции на 10 единиц.

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

Третья задача анализа на чувствительность

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

Рассмотрим такую целевую функцию

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

Эта прямая проходит через точку (0,0) — начало координат — при любых значениях . Условно «разрешим» параметру принимать также значения . Уравнение (2.2) перепишем в виде

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

Таким образом, когда , прямая

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

Пусть . Тогда, если вектор направлен по оси в отрицательную сторону (справа налево). При вектор с направлен по оси вертикально вверх. При вектор направлен по оси в положительную сторону (слева направо) (рис. 2.10). Вращение происходит по часовой стрелке. На рис. 2.10 показано также, как происходит вращение вектора при других сочетаниях знаков коэффициентов .

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

где — заданные числа; — параметр, .

Обратимся к целевой функции

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

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

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

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

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

Максимум целевой функции будет достигаться в вершине , в которой

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

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

Уравнение прямой

Уравнение линии уровня

Отсюда . Итак, когда , максимум достигается во всех точках отрезка и равен 1000.

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

откуда

Наконец, если формально положить , то можно назвать оптимальную вершину — это снова вершина .

Подведем итоги.

1. достигается во всех точках отрезка и равен 700.
2. достигается в вершине (35; 7,5) и равен
3. Оптимальными являются точки отрезка ,
4. . Оптимальная точка — вершина (150/7; 100/7),
5. Максимум достигается в вершине .

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

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

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

Рассмотрим ограничение по запасам сырья из нашего примера

Заменим константу 2 переменной и рассмотрим уравнение прямой

Будем менять коэффициент от 0 до . Прямая (2.4) проходит через точку (0; 25) при любых значениях коэффициента . Когда меняется от 0 до , прямая (2.4) совершает поворот на 90° из начального горизонтального положения ( = 0) в конечное вертикальное . Легко убедиться, что вращение происходит по часовой стрелке (рис. 2. 12).

Когда достигается в точке (35; 70/3): если продукция совсем не требует расхода сырья, ее нужно изготовить как можно больше. Но ограничения не позволяют изготовить более 35 единиц продукции . Оптимальное значение находится из уравнения

Если

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

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

Значит, вершина является оптимальной, пока значения лежат в интервале (4/21; 2). Координаты вершины :

Как только значение превзойдет 2, оптимальная точка переместится в вершину . Так будет, пока вершина не сольется с вершиной (15,10). При этом коэффициента равен (100-4 * 10)/15 =4.

Итак, если 2 < < 4, максимум достигается в точке . Ее координаты можно найти, решив систему уравнений

Отсюда

Когда

Если становится больше 4, от допустимой области остается только треугольник . Оптимальная вершина — , ее координаты таковы:

определяется из условия

Тогда

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

Значит, если

допустимая область пуста, ЗЛП не имеет решения.

Подведем итоги.

1. Оптимальная вершина —
2. Оптимальная вершина — . Она лежит на пересечении прямых . Координаты вершины
3. . Оптимальное решение достигается во всех точках отрезка . Вершина (150/7; 100/7) лежит на пересечении прямых Вершина (35; 7,5) лежит на пересечении прямых .
4. . Максимум целевой функции достигается в точке с координатами . Точка лежит на пересечении прямых .
5. . Оптимальная вершина-. Точка лежит на пересечении прямых .
6. . Допустимая область пуста, задача не имеет решения.

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

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

Задачу (3.1) — (3.2) можно записать компактней. Обозначим через

-мерный вектор неизвестных; через

-мерный вектор коэффициентов целевой функции; через

-мерный вектор правых частей; через

матрицу размера коэффициентов системы линейных уравнений (3.2).

Тогда задача (3.1) — (3.2) записывается так

где — -мерный нуль-вектор; — скалярное произведение векторов и .

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

Чтобы представить задачу (3.1) — (3.2) в канонической форме, нужно уметь:

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

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

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

Переход от неравенств к уравнениям. Рассмотрим неравенство

Пусть вектор

некоторое решение этого неравенства. Тогда

Обозначим разность

через . Тогда и вектор

решение уравнения

Пусть теперь вектор

есть решение уравнения

Так как , то вектор

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

Установлено взаимно однозначное соответствие между всеми решениями неравенства (3.3) и уравнения (3.4). В этом смысле неравенство (3.3) эквивалентно уравнению (3.4).

Так как в целевую функцию переменная не входит, то значения на соответствующих друг другу решениях неравенства (3.3) и уравнения (3.4) совпадают. Другими словами, неравенство

приводится к уравнению

если прибавить дополнительную неотрицательную переменную к левой части неравенства.

Аналогично из неравенства

получается эквивалентное уравнение

Для этого из левой части неравенства (3.5) следует вычесть дополнительную неотрицательную переменную .

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

Как удовлетворить требованию неотрицательности переменных

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

где

Система уравнений (3.2) примет вид

Вместо целевой функции

рассмотрим целевую функцию

Любому решению

системы (3.2) можно поставить в соответствие бесконечно много решений

системы (3.7), (3.7′), где

Но для всякого такого решения значение целевой функции (3.8) на нем равно

т.е. равно значению целевой функции (3.1) на решении .

Обратно, каждому решению

системы (3.7), (3.7′), ставится в соответствие решение

системы (3.2), где

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

Поэтому, если

оптимальное решение задачи (3.7), (3.7′), (3.8), максимизирующее целевую функцию (3.8), то вектор

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

Пример задачи с решением:

• Пример №13. Привести к каноническому виду следующую ЗЛП

Решение системы линейных уравнений по методу Гаусса (методу исключения неизвестных)

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

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

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

Используя перечисленные преобразования, систему (3.9) можно привести к виду, для которого описание множества решений системы (3.9) не представляет труда. Для этого в каждом Уравнении нужно оставить переменную, которая исключается из всех остальных уравнений системы. Такая переменная называется базисной переменной данного уравнения. Базисная переменная входит в свое уравнение с коэффициентом 1, во все остальные уравнения эта переменная входит с коэффициентом 0. Любую переменную можно сделать базисной в любом уравнении.

Пример задачи с решением:

• Пример №14. Рассмотрим такую систему уравнений

Опорные решения

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

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

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

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

Система (3.13) не позволяет получить ОР. Если положить

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

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

ОР таково:

Коротко это можно записать так:

Сделаем теперь базисной переменной второго уравнения. Поделим все коэффициенты второго уравнения на 5/7 и затем исключим из первого уравнения. Получим систему

Соответствующее OP:

Переход от одного опорного решения к другому

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

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

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

Вычисления новых коэффициентов удобно свести в таблицу (табл. 3.1). Покажем расчеты на примере. Обратимся к системе (3.18) и заменим во втором уравнении базисную переменную на переменную .

В табл. 3.1 «упакована» система уравнений. Но в строках и столбцах стоят только коэффициенты при переменных, обозначения переменных вынесены в первую строку.

В части I табл. 3.1 записана система (3.18), в части II — преобразованная система. Базисная переменная заменена на переменную .

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

В части II табл. 3.1 можно заполнить вторую строку.

Пересчитаем элементы первой строки.

Во второй строке части I табл.3.1 в скобках записаны отношения Поэтому сразу можно записать:

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

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

Теперь можно указать новое OP:

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

Вырожденные и невырожденные опорные решения

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

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

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

Если считать базисной переменйой первого уравнения переменную , получим OP = (1; 0; 0; 0); если считать, что базисная переменная первого уравнения — это , получается ОР = (0; 0; 1; 0). Оба эти ОР вырожденные, только одна базисная переменная больше нуля. После умножения на -2 второго уравнения и исключения из первого система приводится к виду

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

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

Рассмотрим каноническую ЗИП с системой ограничений, приведенной к стандартному виду.

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

где через обозначены соответственно числа:

Числа

называются оценками свободных переменных

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

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

Вектор

это вектор коэффициентов при переменной в системе (3.23).

Число — это скалярное произведение векторов и , где вектор

состоит из правых частей системы (3.22).

Число — это коэффициент при свободной переменной в целевой функции .

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

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

В первой строке табл. 3.2 над переменными

записаны соответствующие коэффициенты целевой функции.

Число записано в последней строке столбца правых частей.

Числа

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

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

Итак, после исключения переменных и целевая функция такова:

Подчеркнем, что формулы

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

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

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

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

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

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

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

Тогда

На OP = (0,0,0, 4, 6) целевая функция равна -6. Можно ли увеличить значение ? Можно, если оставить, например, и равными нулю, а переменную сделать больше нуля. Тогда целевая функция возрастет, ведь

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

Переменная остается неотрицательной, пока верно неравенство Когда

Целевая функция увеличилась на 16. Новое ОР — = (0,4, О, 0, 18). Теперь базисными переменными стали переменные и . В табл. 3.3 показаны соответствующие преобразования.

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

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

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

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

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

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

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

Для любой базисной переменной имеем:

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

Аналогично формулируется признак неограниченности целевой функции снизу.

, если существует такая свободная переменная , что а все коэффициенты

В этом случае

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

Попытаемся найти минимум целевой функции Для чего возвратимся к выражениям (3.28), (3.29) и к части I табл. 3.3.

Из (3.28) следует, что можно сделать меньше числа -6, если оставить переменные равными 0, а переменную сделать больше 0. Увеличивать переменную беспредельно нельзя. Если , то базисные переменные выражаются через так:

поэтому максимально возможное значение = 6, тогда переменная обратится в 0. Это значит, что получено новое ОР — = (0; 0; 6; 16; 0), на котором

Базисные переменные этого OP—, ; свободные переменные — . В табл. 3.4 преобразования выглядят следующим образом:

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

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

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

Рассмотрим следующую ЗЛП

Система (3.31) такова, что — базисная переменная первого уравнения, — второго. Соответствующее ОР — вектор = (6; 0; 0; 0; 2), целевая функция на нем равна = -3 * 6 — 2 х 2 = -22.

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

Тогда

Можно ли подобрать такое допустимое решение системы (3.31), на котором целевая функция была бы меньше -22? Нельзя! И это сразу видно из (3.32). Когда все свободные переменные равны нулю, = -22. Но стоит хотя бы одной свободной переменной стать больше нуля, как сразу увеличится, в (3.32.) все свободные переменные входят с положительными коэффициентами. Итак, = -22, достигается минимальное значение целевой функции на ОР = (6; 0; 0; 2).

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

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

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

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

Соответствующие ОР являются оптимальными.

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

Переменную можно увеличивать до тех пор, пока обе переменные неотрицательны. Переменная станет равной нулю, когда = 3; переменная станет равной нулю, когда = 2. Значит, не может быть больше 2. При = 2 получается новое ОР: =(2; 2; 0; 0; 0).

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

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

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

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

Из уравнения

следует, что обращается в 0, когда

Следовательно, та переменная обращается в 0 первой, для которой отношение (3.36) минимально. В только что рассмотренном примере min (6/2; 2/1) = 2, достигался он на отношении, соответствующем базисной переменной (базисной переменной второго уравнения). Поэтому переменная сменила во втором уравнении в качестве базисной переменную .

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

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

Так как

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

Очередное ОР:

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

Обратимся к табл. 3.6. Не будем больше явно выписывать выражения для — они легко определяются по таблице.

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

Так как

то переменная будет только возрастать при увеличении , а переменная будет уменьшаться. Она уменьшится до нуля, когда станет равной 2,4/1 = 2,4. На новом OP = (0; 0; 2,4; 2,8; 0) целевая функция равна -6,8 + 5 х 2,4 = 5,2.

Перейдем к табл. 3.7, где записана стандартная форма системы уравнений при ОР , когда базисными являются переменные (в первом уравнении) и (во втором уравнении).

Оценки всех свободных переменных положительные,

Целевую функцию нельзя более увеличить. Оптимальные значения переменных:

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

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

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

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

Новое значение переменной равно числу

а новое значение равно числу

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

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

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

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

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

Теперь все оценки свободных переменных положительны, поэтому ясно, что на векторе = (0; 4; 0; 2; 2) целевая функция достигает максимума.

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

Пример задачи с решением:

• Пример №15. Общий способ избавления от вырожденности

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

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

Шаг 1. Получить исходное ОР данной задачи.

Шаг 2. Проверить, выполняется ли для данного ОР признак оптимальности. Если это так, оптимальное решение получено, конец. В противном случае перейти к шагу 3.

Шаг 3. Проверить, выполняется ли для данного ОР признак неограниченности целевой функции в допустимой области. Если это так, задача не имеет решения. Конец. В противном случае перейти к шагу 4.

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

Шаг 5. Выбрать уравнение, в котором заменяется базисная переменная. Номер этого уравнения определяется по правилу минимума:

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

Шаг 6. Перейти к новому ОР, используя формулы (3.20).

Шаг 7. Перейти к шагу 2.

Решение оформляется в так называемых симплекс-таблицах. Построенные ранее табл. 3.1-3.13 являются симплекс-таблицами.

Так как число ОР конечно, через конечное число шагов алгоритм закончит работу либо на шаге 2, либо на шаге 3.

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

Описанию способа получения исходного ОР посвящен следующий параграф.

Получение исходного ОР. Метод искусственного базиса

Пусть система уравнений ЗЛП приведена к каноническому виду

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

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

В каждое из уравнений системы (4.1) добавлена искусственная базисная переменная. ЗЛП (4.2) — (4.3′) можно начать решать симплекс-методом. Относительно решения задачи (4.2) — (4.3′) можно сказать следующее.

1. Целевая функция ограничена снизу числом 0, , ведь по условию . Следовательно, случай невозможен, задача (4.2) — (4.3′) всегда имеет решение.
2. Если , то система (4.1) не имеет ни одного решения, уравнения (4.1) несовместны: если — допустимое решение системы (4.1), то — допустимое решение системы (4.3). Но , противоречие с предположением .
3. Если , то все искусственные переменные равны 0. Следовательно, в оптимальном ОР задачи (4.2) — (4.3′) базисными являются переменные системы (4.1). Тогда искусственные переменные можно просто отбросить и перейти к системе (4.1), записанной в стандартной форме.

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

Пример задачи с решением:

• Пример №16. Решить ЗЛП

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

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

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

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

Пример задачи с решением:

• Пример №17. В табл. 4.3 стоит оптимальное ОР, на котором целевая функция достигает своего максимум

Об анализе на чувствительность

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

Примеры задач с решением:

• Пример №18. Для изготовления изделий требуется сырье трех видов
• Пример №19. Решить симплекс-методом

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

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

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

1. В задаче (1) неизвестных и ограничений (без учета условий неотрицательности), в задаче (2) неизвестных и ограничений (без учета условий неотрицательности). Ограничения задачи (1) находятся во взаимно однозначном соответствии с переменными задачи (2). Переменные задачи (1) находятся во взаимно однозначном соответствии с ограничениями задачи (2). Переменные задачи (1) обозначим через ; переменные задачи (2) — через .
2. Матрицы ограничений задач (1) и (2) взаимно транспонированы. Строка коэффициентов системы ограничений задачи (1)— это столбец коэффициентов системы ограничений задачи (2) и наоборот. Если — это коэффициенты при переменной в -ом ограничении задачи (1), , то в задаче (2) коэффициент стоит при переменной в -м ограничении.
3. Правые части системы ограничений задачи (1) — это коэффициенты целевой функции задачи (2); коэффициенты целевой функции задачи (1) — это правые части системы ограничений задачи (2). Если — правая часть -го ограничения задачи (1), то — коэффициент при в целевой функции задачи (2), . Если — коэффициент при в целевой функции задачи (1), то — правая часть -го ограничения задачи (2 ), .
4. Каждому ограничению-неравенству задачи (1) соответствует условие неотрицательности ассоциированной с этим ограничением переменной задачи (2). Каждому ограничению-равенству задачи (1) соответствует переменная задачи (2) без ограничений на знак. Наоборот, каждому ограничению-неравенству задачи (2) соответствует неотрицательная переменная задачи (1), каждому ограничению-равенству задачи (2) соответствует переменная задачи (1) произвольного знака.

Задача (1) называется двойственной задаче (2); задача (2) — двойственной задаче (1).

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

Примеры задач с решением:

• Пример №20. Построить задачу, двойственную следующей ЗЛП
• Пример №21. Любую ЗЛП можно привести к каноническому виду

Несколько замечаний об умножении матриц

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

Вектор — частный случай матрицы. В зависимости от ситуации, вектор можно считать вектор-строкой (1 строка и столбцов) или вектор-столбцом ( строк, 1 столбец).

Так, в записи векторы и — это вектор-столбцы. Это же равенство можно записать так: , но теперь и — вектор-строки.

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

Произведение матриц транспонируется по правилу

Транспонированная вектор-строка — это вектор-столбец; транспонированный вектор-столбец — это вектор-строка. В частности, система ограничений задачи (5.4): , где и — это вектор-столбцы, транспонируется так: , где и уже вектор-строки. Далее будут использованы обе возможности записи системы ограничений в матрично-векторной форме.

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

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

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

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

Столбцы матрицы — это столбцы коэффициентов при переменных .

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

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

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

Если векторы и неотрицательны, , то

, где — квадратная матрица с строками.

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

Теорема 1 (основное неравенство теории двойственности).

Если и — произвольные допустимые решения пары двойственных задач (5.3), (5.4), то

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

Следствие 1. Если допустимые решения и пары двойственных задач (5.3) и (5.4) таковы, что , то и — оптимальные решения этих задач.

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

Следствие 2. Если целевая функция задачи (5.3) не ограничена сверху на допустимом множестве задачи (5.3), то у задачи (5.4) нет ни одного допустимого решения. Если целевая функция задачи (5.4) не ограничена снизу на допустимом множестве задачи (5.4), то у задачи (5.3) нет ни одного допустимого решения.

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

Первая теорема двойственности

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

Будем предполагать, что известно оптимальное решение задачи (5.3). Чтобы провести доказательство в другую сторону, нужно привести задачу (5.4) к каноническому виду.

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

Примеры задач с решением:

• Пример №23. В табл. 5.1 показано оптимальное решение следующей ЗЛП
• Пример №24. Рассмотрим такую ЗЛП

Вторая теорема двойственности

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

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

Тогда

В силу допустимости векторов

можно записать такую цепочкуравенств:

Скалярное произведение неотрицательных векторов

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

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

Условия (5.10) называются условиями дополняющей нежесткости.

Другими словами, если переменная задачи (5.3) отлична от нуля, соответствующее ей -e ограничение двойственной задачи обращается в строгое равенство.

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

Примеры задач с решением:

• Пример №24.2. Найти оптимальное решение ЗЛП
• Пример №25. Дан вектор = (3; 0; 1; 3). Определить, является ли он оптимальным решением следующей задачи
• Пример №26. Сформулируем условия дополняющей нежесткости для симметричной пары двойственных задач.

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

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

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

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

Пример задачи с решением:

• Пример №27. Рассмотрим такую ЗЛП

Двойственность и анализ на чувствительность

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

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

Применим метод искусственного базиса (табл. 5.5).

Оптимальные значения переменных:

Кроме того,

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

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

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

Контроль:

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

Изменение значений правых частей системы ограничений

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

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

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

Обе правые части по-прежнему больше 0. Оптимальное решение ЗЛП

дается вектором

Изменение коэффициентов целевой функции

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

Включение в исходную модель дополнительных переменных

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

то в матрице появляются новые столбцы; образующие матрицу :

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

В последней симплекс-таблице матрица расширится на матрицу

а у вектора оценок появятся новые компоненты

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

Пусть, например, задача (5.26) изменилась так:

Здесь

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

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

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

Пусть в систему ограничений задачи (5.30) добавилось неравенство . Превратим неравенство в уравнение . Переменная становится базисной переменной третьего уравнения. Чтобы добавить это уравнение в оптимальную симплекс-таблицу, нужно выразить базисные переменные и через свободную переменную (см. табл. 5.5, ч. III):

Уравнение

примет вид

Последняя симплекс-таблица станеттакой (табл. 5.6):

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

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

Математическая модель транспортной задачи (ТЗ) рассматривалась в главе 1. Повторим ее описание.

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

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

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

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

Ограничения (6.2) называют ограничениями по запасам (их штук). В каждом таком ограничении записано условие полного использования запасов данного поставщика.

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

Любую открытую

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

Условие ТЗ удобно записывать в матрице, которая называется матрицей перевозок. В ней + 1 строка и + 1 столбец. В первой строке указаны величины потребностей, в первом столбце — значения запасов. В клетках внутренней матрицы (их штук) записывают стоимости перевозок и сами перевозки. Стоимости перевозок условимся записывать в правом верхнем углу клеток. Нумеровать будем только строки и столбцы внутренней матрицы.

Ниже приведена матрица перевозок закрытой ТЗ с тремя поставщиками и пятью потребителями (табл. 6.1).

Если бы, например, потребность равнялась не 60, а 40, нужно было бы ввести еще одного потребителя с потребностью и с нулевыми стоимостями . Матрица перевозок тогда станет следующей (табл. 6.2).

Запишем математическую модель первой из указанных задач. В ней 3×5 = 15 переменных.

Методы получения исходного допустимого решения ТЗ

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

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

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

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

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

Целевая функция равна:

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

Минимальное значение стоимости равно 2, таких стоимостей 3:

Начнем, например, с перевозки . Максимально возможное значение равно 10. Полагаем = 10 и вычеркиваем первый столбец. Запасы первого поставщика теперь равны 20. Обратимся к перевозке Ее нужно положить равной 20, так как . Теперь вычеркиваются первая строка и пятый столбец. Далее полагаем и вычеркиваем третью строку. Четвертому потребителю требуется доставить еще 10 единиц товара. В матрице остались не-вычеркнутыми вторая, третья, четвертая клетки второй строки. Минимальная стоимость в невычеркнутых клетках равна 4 . Полагаем . Затем полагаем

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

Задача, двойственная к транспортной задаче. Соотношения двойственности и описание метода потенциалов

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

Дадим переменным сквозную нумерацию

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

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

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

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

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