Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. E - Ученики, которые не изучают ничего, кроме одного языка программирования
  2. I. 1.1. Пример разработки модели задачи технического контроля.
  3. I. 3.1. Двойственная задача линейного программирования.
  4. I.2. Структура оптимизационных задач
  5. I.5.3. Подготовка данных для задачи линейного программирования.
  6. I.5.4. Решение задачи линейного программирования.
  7. I.5.5. Просмотр и анализ результатов решения задачи.

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

Превращение max в min и наоборот.

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

,

то, умножая её на (- 1), приведем её к виду

,

так как смена знака приводит к смене на .
Аналогично можно заменить на .

Смена знака неравенства.

Если ограничение задано в виде

,

то, умножая на (- 1), получим:

.

Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно.

Превращение равенства в систему неравенств.

Если ограничение задано в виде

,

то его можно заменить эквивалентной системой двух неравенств

,

,

или такой же системой неравенств со знаками больше либо равно.

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

Превращение неравенств в равенства.

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

(1.16)

Здесь первые r ограничений имеют вид неравенств со знаком меньше либо равно

затем идет группа неравенств со знаком больше либо равно

и, наконец, группа ограничений со знаком =.

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

(1.17)

,

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

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

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

Пример

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

Введем дополнительные переменные . Переводя max в min, запишем задачу в виде

что и дает эквивалентную задачу в канонической форме.


Дата добавления: 2015-10-26; просмотров: 164 | Нарушение авторских прав


Читайте в этой же книге: Доказательство | Доказательство | Переход от вершины к вершине |
<== предыдущая страница | следующая страница ==>
Стандартная и каноническая формы задачи линейного программирования| А. Привести к канонической форме следующие задачи линейного программирования.

mybiblioteka.su - 2015-2024 год. (0.006 сек.)