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

Приведение задач ЛП к стандартной форме

ББК 22.161 | Понятие математической модели. Математическая модель в задачах линейного программирования (ЛП) | Примеры задач ЛП | Теоретическое введение | Методика выполнения работы | Принцип работы симплекс-метода | Определение начального допустимого решения | Определение оптимального решения на основе симплекс-таблиц | Решение задач линейного программирования средствами табличного процессора Ехсеl | Анализ оптимального решения на чувствительность |


Читайте также:
  1. Cитуационная задача.
  2. Cитуационная задача.
  3. Cитуационная задача.
  4. I. . Психология как наука. Объект, предмет и основные методы и психологии. Основные задачи психологической науки на современном этапе.
  5. I. Учебные задачи курса, рассчитанные на 10 учебных семестров
  6. I.2. Основные задачи на период с 2006 по 2020 годы
  7. II. Место педагогики в системе наук о человеке. Предмет и основные задачи педагогики

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

Для большинства методов решения задач ЛП требуется предварительно привести задачу к стандартной (канонической, нормальной) форме. Задача (или ее математическая модель) представлена в стандартной форме, если она соответствует следующим условиям:

· Целевая функция подлежит максимизации;

· Все ограничения имеют вид равенств;

· На все переменные накладываются ограничения неотрицательности.

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

Для преобразования ограничения «больше или равно» в равенство (т.е. в ограничение «равно»), необходимо вычесть из левой части ограничения дополнительную переменную. Для преобразования ограничения «меньше или равно» в равенство необходимо прибавить к левой части ограничения дополнительную переменную. На все переменные, используемые для приведения задачи к стандартной форме, накладываются ограничения неотрицательности. Переменные, вычитаемые из ограничений «больше или равно» для их приведения к стандартной форме называются избыточными, а переменные, прибавляемые к ограничениям «меньше ли равно» - остаточными.

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

Приведем к стандартной форме задачу из примера 1.1. Из ограничений «больше или равно» необходимо вычесть избыточные переменные, к ограничению «меньше или равно» - прибавить остаточную переменную. Целевая функция задачи подлежит максимизации, и на все переменные накладывается ограничение неотрицательности; поэтому никаких других преобразований не требуется. Математическая модель задачи в стандартной форме будет иметь следующий вид:

x1 – x3 =200

x2– x4 =100

0,5x1+1,2x2 +x5=600

x1 0; x2 0

 

Е=25x1+40x2→ max

Здесь переменные x3, x4 – избыточные, x5 остаточная.

Примечание. Все переменные, которые вводятся в математическую модель для ее приведения к стандартной форме, имеют физический смысл. Так, в рассмотренном примере переменные x3 и x4 обозначают количество кислот, которое будет выпущено сверх государственного заказа. Переменная x5 обозначает, насколько количество опасных отходов, образующихся при производстве кислот, будет меньше максимально допустимой величины (600 т).

Приведем к стандартной форме задачу из примера 1.2. В ней имеются три ограничения «больше или равно». В каждое из них необходимо ввести избыточную переменную. Целевая функция задачи подлежит минимизации, ее необходимо умножить на (– 1), чтобы перейти к целевой функции, подлежащей максимизации. Математическая модель задачи в стандартной форме будет иметь следующий вид:

x1 – x3 =200

x2– x4 =100

25Х1+40x2 –x5=20000

x1 0; x2 0

 

–Е= –0,5x1–1,2x2 → max.

 


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


<== предыдущая страница | следующая страница ==>
Графический метод решения задач ЛП| Порядок выполнения работ

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