- ЛАГРАНЖА ИНТЕРПОЛЯЦИОННАЯ ФОРМУЛА
- ЛАГРАНЖА ИНТЕРПОЛЯЦИОННЫЕ КОЭФФИЦИЕНТЫ
- ЛАГРАНЖА МЕТОД
- ЛАГРАНЖА ТЕОРЕМА
- ЛАГРАНЖА УРАВНЕНИЕ
- ЛАГРАНЖА ФОРМУЛА
- ЛАПЛАСА ОПЕРАТОР
- ЛАПЛАСА ПРЕОБРАЗОВАНИЕ
- ЛАПЛАСА ТЕОРЕМА
- ЛАПЛАСА ТЕОРЕМЫ
- ЛАПЛАСА УРАВНЕНИЕ
- ЛАПЛАСА ФОРМУЛА
- ЛЕБЕГА ИНТЕГРАЛ
- ЛЕБЕГА МЕРА
- ЛЕВАЯ КАСАТЕЛЬНАЯ
- ЛЕВАЯ ПРОИЗВОДНАЯ
- ЛЕЖАНДРА МНОГОЧЛЕНЫ
- ЛЕЖАНДРА СИМВОЛ
- ЛЕЙБНИЦА ФОРМУЛА
- ЛЕКСИКОГРАФИЧЕСКИЙ МЕТОД
- ЛЕММА
- ЛЕМНИСКАТА
- ЛЕМУАНА ТОЧКА
- ЛИ ГРУППА
- ЛИНЕЙКА
- ЛИНЕЙНАЯ АЛГЕБРА
- ЛИНЕЙНАЯ ВЕКТОР-ФУНКЦИЯ
- ЛИНЕЙНАЯ ГРУППА
- ЛИНЕЙНАЯ ЗАВИСИМОСТЬ
- ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ
- ЛИНЕЙНАЯ КОМБИНАЦИЯ
- ЛИНЕЙНАЯ ОБОЛОЧКА
- ЛИНЕЙНАЯ ФОРМА
- ЛИНЕЙНАЯ ФУНКЦИЯ
- ЛИНЕЙНОЕ ОТОБРАЖЕНИЕ
- ЛИНЕЙНОЕ ПРЕОБРАЗОВАНИЕ
- ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
- ЛИНЕЙНОЕ ПРОСТРАНСТВО
- ЛИНЕЙНОЕ УРАВНЕНИЕ
- ЛИНЕЙНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ
- ЛИНЕЙНЫЙ ОПЕРАТОР
- ЛИНЕЙНЫЙ ЭЛЕМЕНТ
- ЛИНЕЙЧАТАЯ ГЕОМЕТРИЯ
- ЛИНЕЙЧАТАЯ ПОВЕРХНОСТЬ
- ЛИНИИ КРИВИЗНЫ
- ЛИПШИЦА УСЛОВИЕ
- ЛИУВИЛЛЯ ТЕОРЕМА
- ЛОБАЧЕВСКОГО ГЕОМЕТРИЯ
- ЛОБАЧЕВСКОГО МЕТОД
- ЛОГАРИФМ
- ЛОГАРИФМИКА
- ЛОГАРИФМИРОВАНИЕ
- ЛОГАРИФМИЧЕСКАЯ БУМАГА
- ЛОГАРИФМИЧЕСКАЯ ЛИНЕЙКА
- ЛОГАРИФМИЧЕСКАЯ ПРОИЗВОДНАЯ
- ЛОГАРИФМИЧЕСКАЯ СПИРАЛЬ
- ЛОГАРИФМИЧЕСКАЯ ФУНКЦИЯ
- ЛОГАРИФМИЧЕСКИЕ ТАБЛИЦЫ
- ЛОГАРИФМИЧЕСКОЕ УРАВНЕНИЕ
- ЛОГИКА МАТЕМАТИЧЕСКАЯ
- ЛОЖНОГО ПОЛОЖЕНИЯ ПРАВИЛО
- ЛОКАЛЬНЫЙ ЭКСТРЕМУМ
- ЛОКСОДРОМА
- ЛОМАНАЯ
- ЛОПИТАЛЯ ПРАВИЛО
- ЛУДОЛЬФОВО ЧИСЛО
- ЛУПА
- ЛУЧ
- ЛЮИЛЬЕ ЗАДАЧИ
- ЛЯПУНОВА ТЕОРЕМА
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах, описываемых системой линейных неравенств и уравнений.
Основная задача Л. п. состоит в
следующем: дана система линейных неравенств и линейных уравнений от переменных и линейная функция от тех же
переменных. Требуется найти такую точку
в пространстве переменных
, которая удовлетворяет заданной
системе неравенств и уравнений и является экстремумом заданной линейной
функции.
Многие вопросы экономики, а также различные задачи других наук в своей математической постановке являются задачами Л. п.
В качестве примера приведем следующую
задачу. «Предприятие выпускает видов изделий из
видов сырья. Заданы числа
,
,
, означающие количество сырья i-го вида, необходимого для производства единицы
продукции вида
.
Известны также наличные запасы сырья (сырье вида
имеется в
количестве
единиц,
). Наконец, заданы цены, по которым предприятие продает
выпущенную продукцию (
— цена единицы изделия i-го вида,
).
Требуется составить план выпуска изделий, т. е. указать, сколько изделий каждого вида следует изготовить с тем расчетом, чтобы, во-первых, хватило бы запасов сырья и, во-вторых, суммарная стоимость произведенной продукции была бы наибольшей».
Если
— планируемые
количества изделий видов
соответственно, то описанная выше задача
имеет следующую математическую постановку.
Найти такие,
что
,
,
и
линейная форма в точке
принимает максимальное значение.
К задаче Л. п. сводятся многие вопросы
технико-экономического содержания, такие, как задача о раскрое материала,
задача о диете, задача о смесях и др. Отдельной главой Л. п. является теория
транспортных задач. В простейшей постановке транспортная задача формулируется
следующим образом: даны запасы (однородного) товара у поставщиков ( — запас i-го поставщика,
), потребности потребителей (
— потребность j-го потребителя,
), а также
тарифы, т. е. числа
,
означающие стоимость перевозки единицы товара от i-го
поставщика к j-му потребителю.
Требуется составить план перевозок с наименьшими транспортными расходами, т. е.
вычислить числа
,
,
, означающие количество перевозимого товара
от i-го поставщика к
j-му потребителю;
при этом
,
и
линейная форма принимает
минимальное значение.
Решение задач Л. п. может быть проведено
с помощью так называемого симплексного
метода. Сущность этого метода состоит в следующем. Множество точек , удовлетворяющих заданной системе
линейных неравенств и уравнений (допустимая область), представляет собой
выпуклое множество, граница которого разделяется на «куски» — грани различных
размерностей. Так, в трехмерном пространстве переменных допустимая область
является многогранником (возможно пустым или незамкнутым), граница которого
состоит из граней (размерность два), ребер (размерность один), вершин
(размерность нуль); n-мерный случай аналогичен трехмерному. Экстремум
линейной формы на выпуклом множестве не может быть во внутренней точке и, если
существует, находится на границе множества. Оказывается, что в задаче Л. п.
экстремум линейной формы совпадает с одной из вершин допустимой области.
Вычисление такой вершины согласно симплексному методу происходит следующим
образом: 1) выбирается начальная вершина; 2) решается вопрос о том, существует
ли вершина соседняя (по ребру) к начальной вершине, с лучшим значением
линейной формы (т. е. с большим значением, если искомый экстремум — максимум, и
с меньшим значением, если экстремум — минимум). Решение этого вопроса
производится по правилам, предписываемым симплексным методом; 3) если такая
вершина есть, то ее выбирают за начальную, и все операции повторяются; если
такой вершины нет, то изучаемая вершина является искомым экстремумом.
Практическое решение задач Л. п. по симплексному методу связано с построением и
пересчетом симплексных таблиц; каждая таблица соответствует вершине допустимой
области.
Л. п. как наука возникла в конце 30-х г. нашего века в трудах советского математика Л. В. Канторовича. В 1958 г. американский математик ван Данциг разработал описанный выше симплекс-метод в современной редакции.