Линейное программирование Основная задача линейного программирования.

Презентация:



Advertisements
Похожие презентации
Линейное программирование Основная задача линейного программирования.
Advertisements

Линейное программирование Двойственность в линейном программировании.
Метод искусственного базиса. Сущность метода Если в системе ограничений, приведенной к каноническому виду, не удается сразу выделить базисные переменные,
Двойственность линейного программирования. Правила построения двойственных задач: 1. Если в исходной задаче целевая функция исследуется на min, то в двойственной.
1 Методы оптимальных решений к.ф.-м.н. ЮрченкоА.А.
Симплекс-метод. Сущность метода Симплекс-метод – универсальный метод решения задач линейного программирования. Суть метода: целенаправленный перебор.
МАТЕМАТИКА ДЛЯ ЭКОНОМИСТОВ Курс лекций для ЭМО-51, МО-51 филиала СПбГИЭУ в Вологде учебный год Автор: ЕГОРОВА.Е.Ю. Часть 9: ОСНОВЫ ОПТИМАЛЬНОГО.
Транспонирование матрицы переход от матрицы А к мат­рице А', в которой строки и столбцы поменялись местами с сохранением порядка. Матрица А' называется.
Абсолютная величина Уравнения с модулем. Определение модуля Модулем (абсолютной величиной) действительного числа х, т.е. | x|, называется само это число,
Основная задача линейного программирования Геометрическая интерпретация.
1 Стандартная задача Матричная форма записи § 1.4. Специальные виды задач ЛП максимизацииминимизации Обозначения.
Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 16. Тема: Линейное программирование. Цель: Ознакомиться.
Решение задач дробно- линейного программирования графическим методом.
Симплекс-метод. Сущность метода Первый шаг. Найти допустимое решение (план), соответствующее одной из вершин области допустимых решений. Второй.
Решение дробно- рациональных уравнений 9 класс. Определение. Уравнение вида где и – целые выражения, называется дробно-рациональным.
Двойственные задачи. Каждой задаче линейного программирования соответствует задача, называемая двойственной или сопряженной по отношению к исходной задаче.
Часть 2 Двойственные задачи Правила построения двойственных задач.
Квадратное неравенство и его решение Методическая разработка учителя Поляковой Е. А.
Тождества. Тождественные преобразования выражений.
Нелинейное программирование Практическое занятие 2.
Транксрипт:

Линейное программирование Основная задача линейного программирования

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

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

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

Правила приведения Рассмотрим теперь те приёмы, которые позволяют произвольные формы задач линейного программирования приводить к указанным выше стандартным формам. 1. Превращение max в min и наоборот. Если целевая функция в задаче линейного программирования задана в виде то, умножая её на (- 1), приведем её к виду так как смена знака приводит к смене min на max. Аналогично можно заменить max на min.,

Правила приведения 2. Смена знака неравенства. Если ограничение задано в виде то, умножая на (-1), получим: Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно.

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

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

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