Конспект лекций по предмету "Модели и методы"

Узнать цену работы по вашей теме


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

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

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

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

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

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

ìа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), строго говоря, тоже являются ограничениями, однако их не принято так называть, поскольку они являются общими для всех задач линейного программирования, а не только конкретной задачи. Любое неотрицательное решение системы уравнений называется допустимым. Допустимое решение, дающее минимум функции ¦, оптимальное решение (если оно существует) не обязательно единственно; возможны случаи, когда имеется бесчисленное множество оптимальных решений. Наконец, саму функцию ¦ часто называют линейной формой или функцией цели.
Казалось бы, т.к. задача линейного программирования ставится как задача минимизации некоторой функции ¦, то можно применить классический прием дифференциального исчисления. Однако частные производные ¦ равны коэффициентам при неизвестных, которые в «нуль» одновременно не обращаются.


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

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме:

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.

Другие популярные конспекты:

Конспект Основные проблемы и этапы развития средневековой философии
Конспект Проблема познаваемости мира. Гносеологический оптимизм, скептицизм, агностицизм. Взаимосвязь субъекта и объекта познания
Конспект Понятие финансовой устойчивости организации
Конспект Внутренняя политика первых Романовых.
Конспект ПРОБЛЕМЫ КВАЛИФИКАЦИИ ПРЕСТУПЛЕНИЙ
Конспект Понятие мировоззрения, его уровни и структура. Исторические типы мировоззрения
Конспект Синтагматические, парадигматические и иерархические отношения в языке
Конспект Тема 1.2. Плоская система сходящихся сил. Определение равнодействующей геометрическим способом 13
Конспект Происхождение человека. Основные концепции антропосоциогенеза. Антропогенез и культурогенез.
Конспект Общая характеристика процессов сбора, передачи, обработки и накопления информации