Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

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

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

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

Возьмем линейное неравенство

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

При этом данная величина является неотрицательной.

Пример

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

При наличии ограничений в виде неравенств

Решение:

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

Для этого изменим знаки коэффициентов целевой функции.

Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).

Переменная х4 вводится в левую часть второго неравенства со знаком «+», так как неравенство имеет вид «≤».

Переменная x5 вводится в левую часть третьего неравенства со знаком «-«, так как неравенство имеет вид «≥».

В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.

Записываем задачу в каноническом виде:

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

2. Найти начальное опорное решение с «единичным базисом» (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

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

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

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

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

Пример 1

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

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

F = 10×1 — 4×3 max

При наличии ограничений в виде неравенств

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

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x5 с коэффициентом +1. В целевую функцию переменная x5 входит с коэффицентом ноль (т.е. не входит).

F = 10×1 — 4×3+0∙x5 max

При наличии ограничений в виде неравенств

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,5,9/15,6) с единичным базисом Б1 = (А4, А5, А6).

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

· Cб = (с1, с2, . , сm ) — вектор коэффициентов целевой функции при базисных переменных

· Xk = (x1k, x2k, . , xmk ) — вектор разложения соответствующего вектора Ак по базису опорного решения

· Ск — коэффициент целевой функции при переменной хк.

Оценки векторов входящих в базис всегда равны нулю.

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

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

В последней строке таблицы с оценками Δk в столбце «А» записываются значения целевой функции на опорном решении Z(X1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -2, Δ3= -9 для векторов А1 и А3 отрицательные.

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

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

Приращение целевой функции находится по формуле:

.

Вычисляем значения параметра θ01 для первого и третьего столбцов по формуле:

Получаем θ01 = 6 при l = 1, θ03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора

и третьего вектора ΔZ3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение

с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Читать еще:  Язык программирования образуют три составляющие

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6.

Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ02 для второго столбца, он равен 7 при l = 2.

Следовательно, из базиса выводим второй вектор базиса А4.

Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение

Б2 = (А3, А2, А5) (таблица 26.3).

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

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

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

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

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

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

Составляющие математической модели

Основой для решения экономических задач являются математические модели.

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

Составление математической модели включает:

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

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X1, X2. Xn).

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

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

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

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

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2. Xn), удовлетворяющий системе ограничений и условиям неотрицательности.

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

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

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

Задача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

  • bi ( i = 1,2,3. m) — запасы каждого i-го вида ресурса;
  • aij ( i = 1,2,3. m; j=1,2,3. n) — затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
  • cj ( j = 1,2,3. n) — прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X1, X2. Xn), где xj ( j = 1,2. n) — объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема xj продукции равны aijxj, поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна cjxj , поэтому целевая функция равна:

Ответ — Математическая модель имеет вид:

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

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

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

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

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

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

  • А — матрица коэффициентов системы уравнений
  • Х — матрица-столбец переменных задачи
  • Ао — матрица-столбец правых частей системы ограничений

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

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

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

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

Возьмем линейное неравенство a1x1+a2x2+. +anxn≤b и прибавим к его левой части некоторую величину xn+1 , такую, что неравенство превратилось в равенство a1x1+a2x2+. +anxn+xn+1=b. При этом данная величина xn+1 является неотрицательной.

Рассмотрим все на примере.

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).
Переменная х4 вводится в левую часть второго неравенства со знаком «+», так как неравенство имеет вид «≤».
Переменная x5 вводится в левую часть третьего неравенства со знаком «-«, так как неравенство имеет вид «≥».
В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:

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

Канонический вид ЗЛП

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

Для единообразия записи ЗЛП вводится так называемая каноническая форма записи.

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

(2.3)

Отметим следующие особенности канонического вида:

1) требуется минимизировать целевую функцию;

2) все линейные ограничения, кроме требований неотрицательности переменных, имеют вид равенств;

3) на все переменные наложены требования неотрицательности.

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

1) Если в ЗЛП требуется максимизировать целевую функцию f, то положим g = — fи потребуем минимизировать функцию g. Получится новая ЗЛП, которая эквивалентна исходной в том смысле, что каждое оптимальное решение исходной задачи будет оптимальным решением новой задачи и наоборот.

2) Предположим, что в ЗЛП есть линейное ограничение вида

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

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

Аналогично, ограничение вида заменяется двумя ограничениями:

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

(2.6)

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

Указанными приемами любая ЗЛП приводится к каноническому виду.

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

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

Теперь получим ЗЛП в каноническом виде:

2.7. Понятие опорного плана ЗЛП.

Пусть ВЛП задана в каноническом виде (2.3 — 2.5). Предположим, что система уравнений (2.4) приведена к жордановой форме с неотрицательными правыми частями:

(2.6)

где .

Приравняв к нулю свободные переменные, получим базисное решение системы (2.4)

(2.7)

В силу условия набор значений переменных (2.7) удовлетворяет и ограничениям (2.5). Поэтому (2.6) является допустимым решением ЗЛП.

Допустимое решение (2.7) называется базисным допустимым решением или опорным планом ЗЛП. При этом говорят, что переменные образуют допустимый базис.

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

Если ЗЛП разрешима, то существует оптимальный опорный план.

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

Назначение сервиса . Онлайн-калькулятор предназначен для перехода ЗЛП к КЗЛП. Приведение задачи к канонической форме означает, что все ограничения будут иметь вид равенств, путем ввода дополнительных переменных.
Если на какую-либо переменную xj не наложено ограничение, то она заменяется на разность дополнительных переменных, xj = xj1 — xj2, xj1 ≥ 0, xj2 ≥ 0.

  • Решение онлайн
  • Видеоинструкция

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

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

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

Решение системы называется базисным, если в нем свободные переменные равны 0, и оно имеет вид:
Xбаз = (0, 0; b1, …, bm), f(Xбаз) = c

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

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

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

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

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

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

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

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

Читать еще:  Системы автоматизированного проектирования и программирования

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

Эти дополнительные переменные y i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).
Например, если бы машины первого вида работали все 18 ч, то x + y = 18, следовательно, y 1 = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y
Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y 1, y 2, y 3≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:
Переменные yi также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y 1 будет означать количество излишнего вещества А в смеси, y 2 –количество излишков вещества В в смеси, y3 – излишки С в смеси.
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения max F = –min (– F ). Посмотрите на рисунок: если в какой-то точке x= x функция y= F(x) достигает своего максимума, то функция y= –F(x), симметричная ей относительно оси OX, в этой же точке x достигнет минимума, причем Fmax = – (–Fmin) при x = x.

Вывод. Для представления задачи ЛП в канонической форме необходимо:

  • неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;
  • если целевая функция F→max (максимизируется), она заменяется на функцию –F→ min (которая минимизируется).

Пример №1 . Следующую задачу ЛП привести к каноническому виду: F(X) = 5x1 + 3x2 → max при ограничениях:
2x1 + 3x2≤20
3x1 + x2≤15
4x1≤16
3x2≤12
Модель записана в стандартной форме. Введем балансовые неотрицательные переменные x3, x4, x5, x6, которые прибавим к левым частям ограничений-неравенств. В целевую функцию все дополнительные переменные введем с коэффициентами, равными нулю:
В первом неравенстве смысла (≤) вводим базисную переменную x3. Во 2-ом неравенстве смысла (≤) вводим базисную переменную x4. В третьем неравенстве вводим базисную переменную x5. В 4-м неравенстве — базисную переменную x6. Получим каноническую форму модели:
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 20
3x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 15
4x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 = 16
0x1 + 3x2 + 0x3 + 0x4 + 0x5 + 1x6 = 12
F(X) = 5x1 + 3x2 + 0x3 + 0x4 + 0x5 + 0x6 → max

Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции
— F = -2x1 + x2 — 4x3 +2x4 → max

4. Соответствующая целевая функция примет вид:
— F = -2x1 + x2 — 4(x8 – x9) +2(x10 – x11) → max

Пример №2 . Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.

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

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

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

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

, , .

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

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

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

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

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

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

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

, , .

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

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

, , .

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

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

, , .

Ссылка на основную публикацию
Adblock
detector