АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. BRP открывает новый виток инновационного развития с выпуском платформы Ski-Doo REV
  2. Data Mining и Business Intelligence. Многомерные представления Data Mining. Data Mining: общая классификация. Функциональные возможности Data Mining.
  3. I Психологические принципы, задачи и функции социальной работы
  4. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  5. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  6. I. Решение логических задач средствами алгебры логики
  7. I. Розв’язати задачі
  8. I. Ситуационные задачи и тестовые задания.
  9. I. Цель и задачи дисциплины
  10. II Формы общения, к вампиризму не относящиеся
  11. II. Основные задачи и функции
  12. II. Основные задачи и функции

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

, или, в векторной форме: ,

где - матрица размера , а - вектор условий (равенств и/или неравенств).

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

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

Различают три основные формы представления (вида) задач линейного программирования:

Стандартный вид задачи на максимум:

, или, в векторной форме: , (4.1)

где , , , .

 

Стандартный вид задачи на минимум:

, или, в векторной форме: . (4.2)

Канонический вид задачи:

, или, в векторной форме: . (4.3)

Отметим, что любая задача линейного программирования может быть представлена в любом из видов (4.1) – (4.3).

Действительно, пусть какое-либо из ограничений имеет вид неравенства . Если его нужно представит в виде неравенства с противоположным знаком, достаточно умножить левую и правую части на "-1": . Если нужно иметь все ограничения в виде равенств, то к левой части неравенства достаточно прибавить некоторую неотрицательную переменную , так называемую невязку, уравнивающую левую и правую части: При этом размерность задачи увеличится на единицу.

Для неравенств вида манипуляции аналогичны (в частности, для превращения его в равенство невязка вычитается).

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



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

Если в задаче требуется максимизировать целевую функцию: , то умножением ее на "-1" можно свести данную задачу к задаче на минимум: , и наоборот.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |


При использовании материала, поставите ссылку на Студалл.Орг (0.006 сек.)