Студопедия

КАТЕГОРИИ:

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



Лекция 4. Задачи линейное программирование

Читайте также:
  1. I. Задачи настоящей работы
  2. I. Цели и задачи проекта
  3. II. Основные цели и задачи Программы, срок и этапы ее реализации, целевые индикаторы и показатели
  4. II. Упражнения и задачи
  5. II. Упражнения и задачи
  6. II. Упражнения и задачи
  7. II. Цели и задачи проекта
  8. III. Для обеспечения проверки исходного уровня Ваших знаний-умений необходимому, предлагаем решить 2 задачи.
  9. III. Для обеспечения проверки исходного уровня Ваших знаний-умений необходимому, предлагаем решить 2 задачи.
  10. IV. Задачи для самостоятельной работы.

План.

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

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

 

4.1. Формы задач линейного программирования и их эквивалентные преобразования[15]

На основе примеров задач линейного программирования можно представить три формы задач линейного программирования в зависимости от наличия ограничений разного типа.

1. Стандартная задача линейного программирования

, или

;

. .

Стандартная задача линейного программирования – это задача, в которой система функциональных и прямых ограничений состоит из одних неравенств, переменные являются неотрицательными, а целевая функция может стремиться как к максимуму, так и к минимуму. Причем, в стандартной ЗЛП на максимум все функциональные ограничения имеют форму «меньше или равно». В стандартной ЗЛП на минимум все ограничения имеют форму «больше или равно».

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

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

;

.

Каноническая задача линейного программирования – это задача, в которой все переменные xi неотрицательны, система функциональных ограничений представляет собой систему уравнений, а целевая функция стремиться к максимуму.

Основные вычислительные методы (симплекс-метод и его модификации) решения задач линейного программирования разработаны именно для канонической задачи.

3. Общая задача линейного программирования. Необходимо максимизировать (или минимизировать) линейную функцию от n переменных x1, ¼, xn вида

при ограничениях

,

,

.

Стандартная задача получается как частный случай общей при k = m, l = n; каноническая задача получается как частный случай общей при k = 0, l = n.

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

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



- переход от задачи на минимум к задаче на максимум и обратно;

- переход от ограничения в виде неравенства «больше или равно» к ограничению в виде неравенства «меньше или равно»;

- переход от ограничения в виде неравенства к ограничению в виде равенства;

- переход от переменных любого знака к неотрицательным переменным.

Переход от задачи на минимум функции g(`X) к задаче на максимум заключается в рассмотрении задачи на максимум функции - g(`X):

.

И наоборот переход от задачи на максимум функции f(`X) к задаче на минимум заключается в рассмотрении задачи на минимум функции - f(`X):

.

Если система ограничений какой-либо задачи включает неравенства разного вида, то необходимо привести исходную ЗЛП к стандартной форме записи, т.е. для ЗЛП на максимум привести все неравенства функциональных ограничений к виду «меньше или равно», а для ЗЛП на минимум – к виду «больше или равно». Для этого используются следующие эквивалентные преобразования:

В задаче на максимум все члены слева и справа от неравенства умножают на (-1), а знак неравенства меняют на противоположный:



исходные неравенства: ;

получаемые в результате преобразования неравенства: .

Аналогичным образом поступают и в задаче на минимум:

исходные неравенства: ;

получаемые в результате преобразования неравенства: .

Для решения ЗЛП в стандартной форме записи необходимо перейти к эквивалентной ЗЛП в канонической форме записи. Переход от неканонической модели (хотя бы одно ограничение является неравенством) к канонической осуществляется введением в каждое неравенство балансовой переменной xn+k. При знаке неравенства £ балансовая переменная вводится в неравенство со знаком плюс, т.к. левая часть неравенства меньше правой. Если знак неравенства ³, то балансовая переменная вводится в неравенство со знаком минус, т.к. левая часть неравенства больше правой. При этом для всех балансовых переменных вводится условие неотрицательности. В целевую функцию балансовые переменные не вводятся.

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

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

Если на переменную xj общей задачи не накладывается ограничение неотрицательности, то для того, чтобы общую задачу свести к стандартной, необходимо ввести новые переменные и и положить . Таким образом неотрицательное значение – 5 можно заменить двумя положительными значениями 10 и 15: – 5 = 10 – 15.

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


Дата добавления: 2014-12-03; просмотров: 339; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Примеры моделей линейного программирования | Геометрическая интерпретация задачи линейного программирования
lektsii.com - Лекции.Ком - 2014-2019 год. (0.013 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты