Общая задача линейного программирования
Общей задачей линейного программирования называется задача, которая состоит в определении максимального или минимального значения функции
, при условиях
a, c, b – заданные величины.
Функция f называется целевой, а условия ограничения bi – ограничениями линейной задачи.
Совокупность чисел x=(x1,x2,…,xj) удовлетворяющих ограничениям задачи называется допустимым решением (планом).
План x*, при котором целевая функция принимает максимальное/минимальное значение, называется оптимальным планом.
Для решения исходной задачи, имеющей вид «» можно преобразовать ограничения равенства в добавлениях его левой части дополнительной неотрицательной переменной, а ограниченное неравенство «» преобразовать в равенство вычитанием из его левой части дополнительной неотрицательной переменной.
Свойство основной задачи линейного программирования
- запись задачи линейного программирования в векторной форме
- план задачи линейного программирования.
План X называется опорным планом основной задачи линейного программирования, если положительные коэффициенты стоят при линейно-независимых векторах Pj.
Опорный план называется невыраждебным, если он содержит ровно m положительных компонент, в противоположном случае он называется выраждебным.
Базисный вектор состоит из значений целевой функции и коэффициентов целевой функции. Для того, чтобы план был оптимальным необходимо, чтобы выполнялось равенство
Опорный план X является оптимальным, если для любого j
Для нахождения оптимального плана составляют симплекс-таблицу. Чтобы проверить будет ли исходный план оптимальным просматривают элементы m+1 строки.
В ней может иметь место 1 из 3 случаев:
1. для j=m+1, m+2…m+n
2. и меньше 0 все соответствующие этому индексу величины aij<0.
3. для некоторых индексов J и для каждого такого J по крайней мере одно из чисел ai<0.
[таблица]
Транспортная задача
Математическая постановка задачи
Постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A1,A2,…,Am в n пунктов назначения B1,B2,…,Bn. В качестве критерия оптимальности берется минимальная стоимость перевозок, либо минимальный объем времени доставки. Тарифы перевозок из пункта i в пункт j обозначаются Cij (стоимость перевозок единицы груза).
- целевая функция.
При решении транспортной задачи следует учитывать, что обратные перевозки исключаются.
Планом транспортной задачи называется неотрицательное решение системы ограничений.
План, при котором целевая функция принимает минимальные значения, называется оптимальным планом транспортной задачи.
Если в системе ограничений стоят знаки равенства и выполняется условие
,
т.е. общее количество запасов равно общему количеству потребностей, то модель такой транспортной задачи называется закрытой.
Задачи нелинейного программирования
Общий вид. Эта задача состоит в том, чтобы определить максимальное/минимальное значение функции F от переменной f(x1,x2,…,xn), при условии, что все переменные удовлетворяют соотношениям:
fi, gi – некоторые функции и переменные
bi – некоторое фиксированное число
Результатом решения задачи будет x=(x1,x2,…,xn), координаты которой удовлетворяют данным соотношениям. Эти соотношения образуют системе ограничений и включают в себя условия неотрицательности переменных.
В отличии от задачи линейного программирования, функция f может быть функцией степенной (квадратной, кубической и т.д.).
Графический способ решения задачи линейного программирования:
Найти область допустимых решений задачи, используя систему ограничеий;
Построить график функций f;
Определяют границы допустимых решений;
Находят точку области допустимых значений через которую проходит график функций f и определяют в ней значение функции.
Метод множества Лагранжа
Рассмотрим частный случай общей задачи нелинейного программирования.
Предполагается, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности переменных и функции f и gi непрерывные вместе со своими частными производными.
Для решения задачи выводят набор переменных , называемых множителями Лагранжа и составляют функцию Лагранжа
Далее находят частные производные и рассматривают систему из n+m переменных.
,
Всякое решение системы уравнений определяет точку , в которой может иметь место экстремум функции .
Алгоритм решения задачи:
Составить функцию Лагранжа;
Найти частные производные от функции Лагранжа и прировнять их к 0;
Решить систему уравнений, найдя точки, в которых целевая функцию может иметь экстремум;
Среди точек, подозрительных на экстремум находят такие, в которых достигается экстремум и находят значение функции в них.
Другие работы по теме:
Методы анализа эффекивности деятельности предприятия
Экономический анализ — это метод исследования и познания объективного действия экономических законов. Метод экономического анализа базируется на диалектическом материализме, что означает изучение материалистической диалектики в единстве анализа и синтеза, индукции и дедукции.
Диагностика деятельности предприятия
Место экономического анализа в системе управления предприятием, организация аналитической работы, оценка потенциала предприятия. Показатели рентабельности, факторный анализ. Результаты технического и социального развития. Использование трудовых ресурсов.
Сущность управленческого учёта
Предмет, метод и задачи управленческого учёта (УУ) Сравнительная характеристика финансового и управленческого учёта Информация в системе управленческого учёта
Лесопатологический мониторинг
"...17. Лесопатологический мониторинг (далее - ЛПМ) - система постоянных наблюдений за состоянием лесного фонда и лесов, не входящих в лесной фонд, а также за неблагоприятными факторами, влияющими на это состояние..."
Методы психологии труда
Метод наблюдения. Метод опроса. Лабораторный эксперимент. Методы построения простых и сложных теоретических объектов. Преобразующие или конструктивные методы психологии труда.
На основании изучения а
Кочерга Н. В. Логистизация транспортно-распределительной системы ресурсного обеспечения мегаполиса
9. работа по общей геологии
Зачеты Экзамены Бакалавры 1 курс Зимняя сессия 1. Иностранный язык 2. Физическая культура 3. Высшая математика 4. Общая геология 5. Введение в специальность?
Отчет 32 с
Пектральная теория операторов, методы гомогенизации, псевдодифференциальные операторы, разностные операторы, квантовая теория рассеяния, дифракция электромагнитных волн
Оптимальная комбинация ресурсов
КОНТРОЛЬНАЯ РАБОТА №1 по дисциплине «Экономико-математические методы и модели» на тему «Оптимальная комбинация ресурсов» Выполнила: студентка гр. О-060500-31
Математические методы исследования в экономике 2
Математические методы исследования в экономике. Вариант № 6 Составить линейную оптимизационную модель и решить любым известным методом Условие: Фирма выпускает три вида изделий. В процессе производства используются три технологические операции. На рисунке показана технологическая схема производства изделий.
Общее представление о математическом моделировании экономических задач
1. Общее представление о математическом моделировании экономических задач 1.1. Определение экономико-математической модели Математические модели экономических задач – это совокупность средств: уравнений, комплексов математических зависимостей, знаковые логические выражения, отображающие выделенные для изучения характеристики объекта, реальные взаимосвязи и зависимости экономических показателей.
Математическая модель распределения информации
1 Математическая модель распределения информации Математическая модель системы распределения информации включает следующие три основных элемента: входящий поток вызовов (требований на обслуживание), схему системы распределения информации, дисциплину обслуживания потока вызовов.
Роль квалиметрии и оценки товара в управлении качеством
Оценка уровня качества объекта и классификация показателей качества рассматриваются в квалиметрии. Квалиметрия - отрасль науки, изучающая и реализующая методы количественной оценки качества. Основные задачи квалиметрии: обоснование показателей качества, разработка методов их определения, расчета и оптимизации, совершенствование типоразмеров и параметрических рядов изделий, разработка обобщенных показателей и обоснование условий их использования в задачах стандартизации и управления качеством.
Мой любимый предмет - математика сочинение-рассуждение
Автор: Сочинения на свободную тему Я часто думаю, что было бы, если бы мы до сих пор не умели писать и считать. Наверное, жизнь была бы очень скучной и однообразной. Например, я очень люблю головоломки, разные математические задачи. Они помогают мне развиваться, и я всегда радуюсь, когда нахожу правильное решение.
Аньези, Мария Гаэтана
Мари́я Гаэта́на Анье́зи (итал. Maria Gaetana Agnesi; 16 мая 1718, Милан — 9 января 1799) — итальянский математик и филантроп. Она происходит из зажиточной купеческой семьи, в которой был 21 ребёнок. Мария Гаэтана была старшей из детей. Её отец был профессором математики, он с детства поддерживал математические способности дочери и позаботился о хорошем образовании Марии Гаэтаны.
Саккери, Джироламо
Джироламо Саккери (итал. Giovanni Girolamo Saccheri; 1667—1733) — итальянский математик, иезуит, создатель первого наброска неевклидовой геометрии.
Методология истории
План Введение 1 Методы исторического исследования Список литературы Введение Методология исторической науки (истории) — специальная историческая дисциплина, которая определяет предмет и объект исторической науки, цель научного исторического познания, изучает научный и социальный статус исторической науки, её дисциплинарное строение, разрабатывает теорию исторического познания (включая общефилософские, гносеологические и эпистомологические основы, принципы, уровни, виды и методы исторического познания).
Информационные технологии в юриспруденции 2
Информационные технологии в юриспруденции Контрольные задания Упражнение 1 Информационные ресурсы, исходя из особенностей их правового режима, можно классифицировать: по виду информации; по режиму доступа; по виду носителя; по способу формирования информационных ресурсов и их распространения; по способу организации хранения и использования; по форме собственности.
Ариабхата I
Ариабхата I (476— ок. 550) — индийский астроном и математик.В сочинении “Ариабхатиам” (499), посвященном астрономии и математике, изложены математические сведения, необходимые для астрономических наблюдений.