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

Оглавление:

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

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

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

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

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

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

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

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

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

Задача № 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. Затем вычисляются Линейное программирование задачи с решением у находится отмеченная звездочкой Линейное программирование задачи с решением-я переменная для включения в базис, вычисляется столбец Линейное программирование задачи с решением (ведущий элемент помечен крестиком), вычисляются новые базисные переменные и определяются их значения, новые обращения и симплекс-множители. Затем итеративная процедура возобновляется. Когда все Линейное программирование задачи с решением станут положительны, минимум будет достигнут.