Линейное программирование_1

Лекция 7 Линейное программирование

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того вр емени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин " линейное программирование " возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не " линейное программирование ", а "линейное планирование", что более точно отражает содержание дисциплины.

Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

Впервые термин "линейное программирование" предложил американский экономист Т.Купманс в 1951 году. В 1975 году. русский математик Л.В.Канторович и Т.Купманс были удостоены Нобелевской премии по экономическим наукам за свой вклад в теорию оптимального распределения ресурсов. Т.Купманс пропагандировал методы линейного программирования и защищал приоритеты Л.В.Канторовича, открывшего эти методы.

История линейного программирования в США уходит корнями в 1947 год, когда Дж.Данциг написал об этом в своей работе. Л.В.Канторович изучал возможность применения математики к вопросам планирования, на основе чего в 1939 году была опубликована его монография "Математические методы организации и планирования производства". Важнейшей находкой (открытием) Л.В.Канторовича явилась возможность четко математически сформулировать важнейшие производственные задачи, что позволяет найти количественный подход к данным задачам, а также их решение численными методами.

Если бы первые работы Л.В.Канторовича получили в свое время должную оценку, то была бы велика вероятность еще большего продвижения линейного программирования в настоящее время. К сожалению, его работа оставалась в тени как в Советском Союзе, так и за его пределами, и, как отмечает Данциг: " ...и за это время линейное программирование стало настоящим искусством."

Оптимальный план любой линейной программы следует автоматически связывать с оптимальными ценами или, согласно Л.В.Канторовичу, с "объективно обусловленными оценками". Это нагромождение слов имело целью повысить "критикоустойчивость" термина. Суть экономического открытия Л.В.Канторовича заключается во взаимосвязи оптимальных решений и оптимальных цен.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше,

состоит в нахождении минимума (или максимума) линейной функции, на неизвестные которой наложены линейные ограничения.

Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.

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

•при наличии математической определенности и количественной ограниченности между изучаемыми переменными величинами и факторами;

•при взаимозаменяемости факторов из-за последовательности расчетов;

•в случае совмещения математической логики с пониманием сущности изучаемых явлений.

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

Всельском хозяйстве с помощью этого метода определяют минимальную стоимость кормовых рационов с учетом заданного количества кормов (исходя из видов и содержащихся в них полезных веществ).

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

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

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

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

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