Общая формулировка задачи линейного программирования
Общая формулировка задачи линейного программирования - Лекция, раздел Образование, Методы и модели
Аналогично Транспортной Задаче Решается Задача Об Оптимизации...
Аналогично транспортной задаче решается задача об оптимизации распределения ресурсов (трудовых, материальных, финансовых) и задача о диете. При всем разнообразии, по своему конкретному содержанию каждая из них была задачей на нахождение наиболее выгодного варианта. С точки зрения математической, в каждой задаче ищутся значения нескольких неизвестных, причем требуется, чтобы:
À эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
Á при этих значениях некоторая линейная функция (линейная форма) от этих неизвестных обращалась в минимум (максимум);
 эти значения были неотрицательными.
Задачами такого рода и занимается линейное программирование.
þ Говоря точнее, линейное программирование - это математическая дисциплина, изучающая методы нахождения наименьшего (или наибольшего) значения линейной функции нескольких переменных, при условии, что последние удовлетворят конечному числу линейных уравнений или неравенств. Общая математическая формулировка задачи линейного программирования выглядит следующим образом.
Дана система линейных уравнений:
ìа11x1+а12x2+ ... +а1nxn = b1
ïа21x1+а22x2+ ... +а2nxn = b2
(I) í ... ... ... ... ... ... ... ...
îаm1x1+аm2x2+ ... +аmnxn = bm
и линейная функция ¦=c1x1+c2x2+ ... +cnxn(II).
Требуется найти такие неотрицательные решения х1 ³ 0, х2 ³ 0 ... хn ³ 0(III) системы (I) при которых функция ¦ принимает наименьшее (наибольшее) значение.
Уравнения (I) называются ограничениями данной задачи, уравнение (II) называется линейной формой, а уравнение (III), строго говоря, тоже являются ограничениями, однако их не принято так называть, поскольку они являются общими для всех задач линейного программирования, а не только конкретной задачи. Любое неотрицательное решение системы уравнений называется допустимым. Допустимое решение, дающее минимум функции ¦, оптимальное решение (если оно существует) не обязательно единственно; возможны случаи, когда имеется бесчисленное множество оптимальных решений. Наконец, саму функцию ¦ часто называют линейной формой или функцией цели.
Казалось бы, т.к. задача линейного программирования ставится как задача минимизации некоторой функции ¦, то можно применить классический прием дифференциального исчисления. Однако частные производные ¦ равны коэффициентам при неизвестных, которые в «нуль» одновременно не обращаются.
Возникновение и развитие системных представлений
Научно-техническая революция привела к возникновению таких понятий, как большие и сложные экономические системы, обладающие специфическими для них проблемами. Необходимость р
Виды подобия моделей
Чтобы некоторая материальная конструкция могла быть моделью, т.е. замещала в каком-то отношении оригинал, между оригиналом и моделью должно быть установлено отношение подобия. Сущес
Адекватность моделей
þ Модель, с помощью которой успешно достигается поставленная цель, будем называть адекватной этой цепи. Адекватность означает,
Понятие операционного исследования
Bпервые математические модели были использованы для решения практической задачи в 30-х годах в Великобритании при создании системы противовоздушной обороны. Для разработки данной си
Математических моделей
Можно выделить следующие основные этапы построения математической модели:
À Определение цели, т.e. чего хотя
W=W (x, a, x)
В соответствии с введенными терминами, математическая модель задачи имеет следующий вид:
W=W (x, a, x) ® max (min) (2.1)
x &
Выпуклые множества
Предварительно дадим некоторые понятия, весьма важные для линейного программирования.
þ множество точек называется выпуклыми,
Линейные неравенства
рассмотрим подробнее системы линейных неравенств и покажем, что решение их тесно связано с понятиями выпуклого многоугольника и выпуклого многогранника.
Транспортная задача
уголь, добываемый в нескольких месторождениях, отправляется ряду потребителей. нам известно, сколько угля добывается в каждом из месторождений, скажем за месяц и сколько его требует
Решения задач линейного программирования
Задачу линейного программирования (ЛП) можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный н
Общая и основная задачи линейного программирования
К математическим задачам линейного программирования приводят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи
Задач линейного программирования
Перепишем основную задачу линейного программирования в векторной форме: найти максимум функции
F=CX (5.5)
при у
Симплексный метод
Симплексный метод или метод последовательного улучшения плана является одним из основных методов решения задач ЛП. название симплексный метод берет от слова «симплекс», которым созд
Анализ симплекс-таблиц
Математическая модель является прекрасным средством получения ответов на широкий круг вопросов, возникающих при планировании, проектировании и в ходе управления производством. Так н
Основные условия и область применения.
В ряде реальных экономических и производственных задач необходимо учитывать изменение моделируемого процесса во времени и влияние времени на критерий оптимальности. Для решения указ
Многокритериальная оптимизация
þ задачи, в которых оптимизацию проводят по нескольким параметрам, называют задачами многокритериальной или векторной оптимизации
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов