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

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

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

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

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

, , .

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

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

1) если знак неравенства , то балансовая переменная вводится со знаком плюс;

2) если знак неравенства , то балансовая переменная вводится со знаком минус;

3) в целевую функцию балансовые переменные не вводятся;

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

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

, , .

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

Каноническая форма исходной задачи будет иметь вид:

, , .

Задания для решения в аудитории

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

, , .

Источник

Переход к канонической форме ЗЛП

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

Математическая модель называется канонической, если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r=m), в системе выделен единичный базис, определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны (b_i ≥ 0).

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

Решение системы называется базисным, если в нем свободные переменные равны 0, и оно имеет вид:
X_баз = (0, 0; b₁, …, b_m), f(X_баз) = c₀

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

Базисное решение называется опорным, если оно допустимо, т.е. все правые части уравнений системы (или неравенств) положительны b_i ≥ 0.

Компактная форма канонической модели имеет вид:
AX = b
X ≥ 0
Z = CX(max)

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

Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных.
Система ограничений (3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y₁≥ 0, y₂≥ 0, y₃≥ 0, y₄ ≥ 0, можно перейти к системе ограничений:

Эти дополнительные переменные y _i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).
Например, если бы машины первого вида работали все 18 ч, то x + y = 18, следовательно, y ₁ = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y y = 6, мы можем из системы ограничений (3.9) сделать вывод, что y₁ = y₂ = y₃ = 0, а y₄ = 12 – 6 = 6. Т. е. машины первого, второго, третьего вида используют свое рабочее время полностью. А вот четвертая машина загружена лишь наполовину, 6 часов, и при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой, сдать в аренду на это время и т.д.
Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.

Рассмотрим задачу о смеси. Система ограничений имеет вид:
Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y ₁, y ₂, y ₃≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:
Переменные y_i также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y ₁ будет означать количество излишнего вещества А в смеси, y ₂ –количество излишков вещества В в смеси, y₃ – излишки С в смеси.
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения max F = –min (– F ). Посмотрите на рисунок: если в какой-то точке x= x₀ функция y= F(x) достигает своего максимума, то функция y= –F(x), симметричная ей относительно оси OX, в этой же точке x₀ достигнет минимума, причем F_max = – (–F_min) при x = x₀.

Источник

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

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

Переменные задачи часто записывают в виде n-мерного вектора:
.

Система ограничений (1.2) может состоять из равенств
,
и неравенств обоих знаков:
, или
.

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

Различные формы задач ЛП

Теорема
Любую общую задачу линейного программирования (1.1) – (1.3) можно привести к каноническому виду (1.4). А любую задачу в канонической форме можно привести к любой из задач в симметричной форме (1.5) или (1.6).

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

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

переводится в равенство, введением дополнительной неотрицательной переменной :
.

Графический метод решения

Свойства решений задач линейного программирования (ЛП) наглядно демонстрирует графический метод решения.

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

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

Свойства решений задач ЛП

Далее приводим более строгую трактовку этих рассуждений.

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

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

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

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

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

Теорема
Угловая точка ОДР (1.2) – (1.3) является решением системы из n уравнений, полученной из (1.2) – (1.3), вычеркиванием части неравенств, и заменой оставшихся неравенств равенствами.

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

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

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

Теорема о числе базисных переменных
При решении задачи линейного программирования в канонической форме ⇑, в любом опорном плане имеется r базисных переменных ⇑. Отсюда следует, что в опорном плане как минимум переменных равны нулю. Здесь n – число переменных; r – ранг матрицы системы ограничений (1.4), из которой определяются значения базисных переменных.

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

Графический метод

Метод перебора вершин

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

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

Решение задачи

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

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

Итак, мы нашли все угловые точки ОДР. Находим в них значения целевой функции.
;
;
;
;
.

Симплексный метод

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

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

Решение задачи

4. Повторяем шаги 2 и 3.

6. Повторяем шаги 4 и 5.

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

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

Решение транспортной задачи методом потенциалов

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

Задача имеет неотрицательных переменных:
.

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

Метод северо-западного угла

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

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

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

Первый опорный план.

Определение потенциалов

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

.

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

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

Цикл с начальной вершиной в заданной пустой клетке – это ломаная, все вершины которой расположены в занятых клетках, кроме одной начальной вершины. И при этом две соседние вершины цикла расположены или в одной строке, или в одном столбце. Потенциалы и контур клетки (1,3).

Второй опорный план.

Определение потенциалов нового плана

Находим оценки свободных клеток по формуле:
.

.

Поскольку отрицательных оценок нет, то план оптимален.

Использованная литература:
С. Гасс. Линейное программирование (методы и приложения). Москва, «Государственное издательство физико-математической литературы», 1961.
Общий курс высшей математики для экономистов. Под общей редакцией В. И. Ермакова. Москва, «ИНФРА-М», 2007.
К. Н. Лунгу. Линейное программирование. Руководство к решению задач. Москва, «ФИЗМАТЛИТ», 2005.
Д. Б. Юдин, Е. Г. Гольштейн. Задачи и методы линейного программирования. Москва, «Советское радио», 1961.

Источник

Содержание:

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

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

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

Построение математической модели экономической задачи включает следующие этапы:

Переменными задачи называются величины

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

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

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

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

Данная запись означает следующее: найти экстремум целевой функции задачи и соответствующие ему переменные X = (). при условии, что эти переменные удовлетворяют системе ограничений и условиям неотрицательности.

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

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

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

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

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

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

В данном случае введены векторы:

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

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

Приведение общей задачи линейного программирования к канонической форме

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

прибавляется величина такая, что переводит неравенство в равенство , где:

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

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

Теорема. Каждому решению неравенства соответствует единственное решение уравнения: и неравенства и, наоборот, каждому решению уравнения: и неравенства соответствует единственное решение неравенства:

Доказательство. Пусть — решение неравенства. Тогда:

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

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

Доказана первая часть теоремы.

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

т.е. удовлетворяет неравенству: что и требовалось доказать.

Если в левую часть неравенств системы ограничений вида

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

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

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

Множества допустимых решений

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

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

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

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

Граничные точки множества образуют его границу. Множество называется замкнутым, если оно содержит все свои граничные точки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

Предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами трех видов С, D и Е в объемах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и представлены в табл. 14.1

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

Тогда прибыль предприятия от реализации изделий А и изделий В составит:

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

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

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

Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями.

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

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

Аналогично построены 2-я и 3-я прямые и найдены полуплоскости, соответствующие 2-му и 3-му неравенству. Точки, удовлетворяющие ограничениям , находятся в первом квадранте. Множество точек, удовлетворяющих всем ограничениям одновременно, является ОДР системы ограничений. Такой областью на графике (рис. 14.1) является многоугольник ОАВС.

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

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

имеет координаты

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

Решив эту систему, получаем, что

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

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

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

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

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

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

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

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

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

Симплекс-метод с естественным базисом

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

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

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

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

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

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

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

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

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

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

Строка называется направляющей, столбец и элемент — направляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам:

а элементы любой другой i-й строки пересчитываются по формулам:

Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:

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

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

Симплексный метод с искусственным базисом (М-метод)

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

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

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

Теория двойственности

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

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

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

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

Переменные двойственной задачи называют объективно обусловленными оценками или двойственными оценками.

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

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

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

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

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Источник