Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-12-21 | 169 |
5.00
из
|
Заказать работу |
|
|
Общей задачей ЛП называется задача, которая формулируется следующим образом:
Найти максимальное (минимальное) значение линейной функции
(2.1)
при условиях
(), (2.2)
(), (2.3)
() (2.4)
где , , — заданные постоянные величины и .
Функция (2.1) называется целевой функцией (или линейной формой) задачи (2.1)-(2.4), а условия (2.2)–(2.4) — ограничениями данной задачи.
Стандартная (или симметрическая) задача ЛП состоит в определении максимума функции (2.1) при ограничениях неравенствах (2.2) и условиях (2.4), где , т.е. имеет вид:
,
(), (2.5)
, ().
Каноническая (или основная) задача ЛП состоит в определении максимума функции (2.1) при ограничениях-равенствах (2.3) и условиях (2.4):
,
(), (2.6)
, ().
Задачу ЛП можно записать более компактно, если ввести обозначения:
— матрица ограничений размерности (),
— вектор-столбец свободных членов,
— вектор-строка коэффициентов целевой функции,
— вектор переменных задачи, который в одних случаях рассматриваем как вектор-строку, а в других — вектор-столбец. Знак транспонирования вектора (строки или столбца) опускаем для сокращения записи.
Тогда стандартная задача (2.5) примет вид:
,
, (2.7)
,
а каноническая задача (2.6) –
,
, (2.8)
.
Здесь (или — в ином обозначении — ) — скалярное произведение векторов c и x, т.е.
.
— произведение матрицы А на вектор-столбец x.
Вектор , удовлетворяющий ограничениям задачи (2.2)–(2.4), называется допустимым решением (или планом). Обозначим множество всех допустимых планов задачи .
Допустимый план , доставляющий экстремум целевой функции, называется оптимальным план ом (решением) задачи. Обозначим множество всех оптимальных планов . Если множества Ø и Ø (не пустые множества), задача ЛП разрешима, в противном случае говорят о неразрешимости этой задачи. Различают два вида неразрешимости:
|
— неразрешимость первого типа (НР1), если множество допустимых планов пусто ( Ø );
— неразрешимость второго типа (НР2), если целевая функция не ограничена на непустом множестве ( Ø).
Любую задачу ЛП можно свести как к стандартной, так и к канонической форме, используя следующие правила:
1) чтобы перейти от минимизации к максимизации целевой функции , следует умножить целевую функцию на (-1) и использовать равенство
,
т.е. задача соответствует задаче
;
2) чтобы изменить в ограничении-неравенстве неравенство на неравенство противоположного смысла, следует умножить обе части неравенства на (–1):
;
3) чтобы перейти от ограничения-неравенства к равенству, нужно ввести дополнительную (слабую) переменную :
,
;
4) чтобы перейти от ограничения-равенства к неравенству, следует заменить это равенство на два противоположных неравенства:
;
5) чтобы исключить свободную переменную (т.е. такую, для которой
нет ограничения на знак), следует ввести две новые неотрицательные переменные , , положив
, , .
Пример. Привести к каноническому виду задачу ЛП:
,
Перейдём к задаче на максимум:
,
введём дополнительные переменные, исключив ограничения-неравенства:
Исключим свободную переменную , используя замену
.
Окончательно получим:
,
|
|
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!