Лекция 7 мин.
Сразу хочу сказать, что здесь никакой воды про линейное программирование, и только нужная информация. Для того чтобы лучше понимать что такое линейное программирование , настоятельно рекомендую прочитать все из категории Математическое программирование.
линейное программирование — математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах 
-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась еще в XIX веке. Приматематическом анализе процесса расширенного производства использовались алгебраические соотношения, анализ их проводился с помощью дифференциального исчисления. Это давало возможность получить общее представление о проблеме.
Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 1924—1925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции.
В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению чисто практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. Стало ясно, что задача не случайная.
В 1939 году Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования.
Изучение подобных задач привело к созданию новой научной дисциплины линейного программирования и открыло новый этап в развитии экономико-математических методов.
В 1949 году американский математик Джордж Бернард Данциг разработал эффективный метод решения задач линейного программирования (ЗЛП) — симплекс-метод.
Термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Он был предложен в середине 1940-х годовДжорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задачоптимизации.
Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.
задачи линейного программирования
Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида :
Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)
,
.
Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства :
,
Основную задачу можно свести к канонической путем введения дополнительных переменных.
Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств .
Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты 
с обратным знаком.
Рассмотрим задачу о максимальном паросочетании в двудольном графе: есть несколько юношей и девушек, причем для каждых юноши и девушки известно, симпатичны ли они друг другу. Об этом говорит сайт https://intellect.icu . Нужно поженить максимальное число пар со взаимной симпатией.
Введем переменные 
, которые соответствуют паре из 
-того юноши и 
-той девушки и удовлетворяют ограничениям:
с целевой функцией 
. Можно показать, что среди оптимальных решений этой задачи найдется целочисленное. Переменные равные 1, будут соответствовать парам, которые следует поженить.
Пусть имеется граф (с ориентированными ребрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме истока и стока, соответственно).
Возьмем в качестве переменных 
— количество жидкости, протекающей через -тое ребро. Тогда
,
где 
— пропускная способность -того ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции 
естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.
Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к двум задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение 
, где 
— величина максимального потока, и решить задачу с новой функцией 
— стоимостью потока.
Эти задачи могут быть решены быстрее, чем общими алгоритмами решения задач линейного программирования, за счет особой структуры уравнений и неравенств.
Имеется некий однородный груз, который нужно перевезти с складов на заводов. Для каждого склада известно, сколько в нем находится груза 
, а для каждого завода известна его потребность 
в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния 
от -го склада до -го завода известны). Требуется составить наиболее дешевый план перевозки.
Решающими переменными в данном случае являются — количества груза, перевезенного из -го склада на -й завод. Они удовлетворяют ограничениям:
Целевая функция имеет вид: 
, которую надо минимизировать.
Есть матрица 
размера 
. Первый игрок выбирает число от 1 до , второй — от 1 до . Затем они сверяют числа и первый игрок получает 
очков, а второй 
очков ( — число, выбранное первым игроком, — вторым). Нужно найти оптимальную стратегию первого игрока.
Пусть в оптимальной стратегии, например, первого игрока число нужно выбирать с вероятностью 
. Тогда оптимальная стратегия является решением следующей задачи линейного программирования:
,
,
(
),
в которой нужно максимизировать функцию 
. Значение в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.
Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом сэкспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранникадопустимых решений при поиске оптимального решения.
Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешенной. Метод эллипсоидов имеет совершенно другую, некомбинаторную природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привел к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).
А как ты думаешь, при улучшении линейное программирование, будет лучше нам? Надеюсь, что теперь ты понял что такое линейное программирование и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Математическое программирование
Из статьи мы узнали кратко, но содержательно про линейное программирование
Комментарии