Letysite.ru

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

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

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

Назначение сервиса . Онлайн-калькулятор предназначен для перехода ЗЛП к КЗЛП. Приведение задачи к канонической форме означает, что все ограничения будут иметь вид равенств, путем ввода дополнительных переменных.
Если на какую-либо переменную 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 . Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.

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

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

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

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

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

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

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

Общая ЗЛП. Канонический вид ЗЛП

2.1. Общая ЗЛПформулируется в виде (1.2). Другими словами, ЗЛП в общем виде ставится как (1.2).

Таким образом, имея дело с ЗЛП, мы будем иметь дело с линейной системой. В теории линейных систем x1, x2, …, xn мы называли неизвестными. В оптимизации функции f(x1, x2, …, xn) они выступают в качестве переменных. Поэтому к ним мы будем применять этот термин. От этого их суть не меняется: необходимо найти (неизвестные) переменные x1, x2, …, xn, при которых целевая функция f(x1, x2, …, xn) достигает экстремума. Также, мы сохраняем терминологию линейных систем: основная и расширенная матрица, совместные системы, ранг системы, базисное решение и т.д. Так же, будем считать, что ранг r системы совпадает с числом m уравнений и неравенств: r=m.

Читать еще:  Событийная модель программирования

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

Если в системе ограничений задачи (1.2) присутствуют только уравнения, а свободные члены в системе ограничений задачи являются неотрицательными, то говорят, что задача имеет канонический вид. Согласно 1.2.2 первой части, любая смешанная система приводится к системе уравнений добавлением дополнительных неотрицательных переменных со знаком «+» в неравенства типа «≤» и со знаком «-» в неравенства типа «≥». Поэтому для приведения к каноническому виду задачи линейного программирования поступаем следующим образом:

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

2) Добавляем в каждое неравенство дополнительные неотрицательные переменные: со знаком «+» в неравенства типа «≤» и со знаком «-» в неравенства типа «≥».

2.2.1. ОЗЛП (1.2) приводится к каноническому виду

2.2.2. ЗЛП (1.4) приводится к каноническому виду

2.2.1. ЗЛП (1.5) приводится к каноническому виду

В любом случае можно считать, что ЗЛП имеет канонический вид

(2.1)

Если A=(aij) — матрица системы ограничений задачи, X=(x1, x2, …, xn) T — столбец переменных, B=(b1, b2, …, bn) T — столбец свободных членов системы ограничений и C=(c1, c2, …, cn) — вектор коэффициентов целевой функции, то задачу (2.1) можно записать в матричной форме:

CX®max(min)

AX=B, XO.

Обозначим через A1, A2, …, An соответственно 1-й, 2-й, …, n-й столбцы матрицы A. Тогда задачу (1.6) можно записать в векторной форме:

CX®max(min)

XO.

2.3. Упражнение. Привести к каноническому виду задачи линейного программирования из предыдущих заданий 1)3), выписать их матрицы ограничений, столбцы свободных членов, векторы условий, векторы коэффициентов целевых функций, и записать задачи в матричной и векторной формах.

Решение. 1г) 4x1+x2®min(max)

Правая часть первого неравенства — отрицательная. Поэтому первое неравенство умножаем на -1:

Теперь все неравенства ограничений имеют тип «£». Поэтому во все эти неравенства вводим дополнительные неотрицательные переменные, соответственно x3, x4, x5:

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

Матрица ограничений (выписываем для канонического вида): , — столбец свободных членов, A1= , A2 = , A3= , A4= , A5= — векторы условий, (4, 1, 0, 0, 0) — вектор коэффициентов целевой функции, × = , ³O — матричная форма записи задачи, x1+ x2+ x3+ x4+ x5=

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

Как организовать дистанционное обучение во время карантина?

Помогает проект «Инфоурок»

КАНОНИЧЕСКАЯ ФОРМА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАМИРОВАННИЯ.

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

эти значения удовлетворяли некоторой системе линейных уравнений и неравенств;

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

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

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

Достигла бы минимального значения.

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

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

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

Выберите книгу со скидкой:

ЕГЭ. География. Новый полный справочник для подготовки к ЕГЭ

350 руб. 163.00 руб.

350 руб. 171.00 руб.

ЕГЭ-2019. География. Теория и практика

350 руб. 213.00 руб.

ОГЭ. География. Большой сборник тематических заданий для подготовки к основному государственному экзамену

350 руб. 197.00 руб.

Читать еще:  Программирование рекурсивных алгоритмов

География. 10-11 классы. Атлас. (Традиционный комплект) (РГО)

350 руб. 106.00 руб.

География. 7 класс. Атлас. (Традиционный комплект)(РГО)

350 руб. 106.00 руб.

География. 5 класс. Атлас. (Традиционный комплект).

350 руб. 106.00 руб.

География. 10-11 классы. Контурные карты. (Традиционный комплект) (РГО)

350 руб. 59.00 руб.

География. 6 класс. Атлас. (Традиционный комплект)(РГО)

350 руб. 106.00 руб.

География. Материки, океаны, народы и страны. 7класс. Атлас

350 руб. 184.00 руб.

География. 9 класс. Контурные карты. (Традиционный комплект) (РГО)

350 руб. 59.00 руб.

География. Начальный курс географии. 6класс. Контурные карты

350 руб. 101.00 руб.

БОЛЕЕ 58 000 КНИГ И ШИРОКИЙ ВЫБОР КАНЦТОВАРОВ! ИНФОЛАВКА

Инфолавка — книжный магазин для педагогов и родителей от проекта «Инфоурок»

Бесплатный
Дистанционный конкурс «Стоп коронавирус»

  • Стус Валентина Дмитриевна
  • Написать
  • 145
  • 19.02.2018

Номер материала: ДБ-1225716

Добавляйте авторские материалы и получите призы от Инфоурок

Еженедельный призовой фонд 100 000 Р

  • 01.03.2018
  • 443
  • 27.02.2018
  • 189
  • 27.02.2018
  • 1659
  • 27.02.2018
  • 200
  • 25.02.2018
  • 296
  • 21.02.2018
  • 180
  • 21.02.2018
  • 180
  • 16.02.2018
  • 147

Не нашли то что искали?

Вам будут интересны эти курсы:

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

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

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

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

; (2.24)

, (2.25)

. (2.26)

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

1) минимизация целевой функции (2.24);

2) запись системы ограничений в виде строгих равенств (2.25);

3) условие неотрицательности на все переменные (2.26);

4) наличие в системе ограничений исходного базиса;

5) неотрицательность всех свободных членов в системе ограничений.

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

1. если исходная ф-я бала на max, то *(-1) и исследуем ее на min

2. Если в неравенстве стоит знак = то со знаком «-»

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

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

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

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

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

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

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

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

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

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

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

Множество наз замкнутым если оно содержит в себе граничные точки

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

Дата добавления: 2018-05-12 ; просмотров: 414 ;

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