рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Вид работы: Лекции
/
Общая формулировка задачи линейного программирования

Реферат Курсовая Конспект

Выберите учебное заведение

Общая формулировка задачи линейного программирования

Общая формулировка задачи линейного программирования - Лекция, раздел Образование, Методы и модели Аналогично Транспортной Задаче Решается Задача Об Оптимизации...

Аналогично транспортной задаче решается задача об оптимизации распределения ресурсов (трудовых, материальных, финансовых) и задача о диете. При всем разнообразии, по своему конкретному содержанию каждая из них была задачей на нахождение наиболее выгодного варианта. С точки зрения математической, в каждой задаче ищутся значения нескольких неизвестных, причем требуется, чтобы:

À эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;

Á при этих значениях некоторая линейная функция (линейная форма) от этих неизвестных обращалась в минимум (максимум);

Â эти значения были неотрицательными.

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

þ Говоря точнее, линейное программирование - это математическая дисциплина, изучающая методы нахождения наименьшего (или наибольшего) значения линейной функции нескольких переменных, при условии, что последние удовлетворят конечному числу линейных уравнений или неравенств. Общая математическая формулировка задачи линейного программирования выглядит следующим образом.

Дана система линейных уравнений:

ìа₁₁x₁+а₁₂x₂+ ... +а₁_nx_n₌b₁

ïа₂₁x₁+а₂₂x₂+ ... +а₂_nx_n₌b₂

(I) í ... ... ... ... ... ... ... ...

îа_m₁x₁+а_m₂x₂+ ... +а_mnx_n₌b_m

и линейная функция ¦=c₁x₁+c₂x₂+ ... +c_nx_n (II).

Требуется найти такие неотрицательные решения х₁ ³ 0, х₂ ³ 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 &

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

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

Значения линейной формы на выпуклом множестве
Предположим, что задана некоторая система из m-линейных неравенств (или уравнений) с n переменными х1, х2, ..., хn. Система нер

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

Решения задач линейного программирования
Задачу линейного программирования (ЛП) можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный н

Общая и основная задачи линейного программирования
К математическим задачам линейного программирования приводят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи

Задач линейного программирования
Перепишем основную задачу линейного программирования в векторной форме: найти максимум функции F=CX (5.5) при у

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

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

Постановка задачи нелинейного программирования
В общем виде задача нелинейного программирования (ЗНП) формируется следующим образом: f (x1, x2, ..., xn) ® max (mi

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

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