1.1. Теоретическая часть о линейном программировании.

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

История линейного программирования: Л.В.Канторович изучал возможность применения математики к вопросам планирования, на основе чего в 1939 году опубликована его монография «Математические методы организации и планирования производства». Важнейшей находкой (открытием) Канторовича явилась возможность четко математически сформулировать важнейшие производственные задачи, что позволяет найти количественный подход к данным задачам, а также их решение численными методами.²

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В общей постановке задача линейного программирования выглядит следующим образом:

Имеются какие то переменные х=(х1,х2,…хn) и функция этих переменных f(x)=f(x1,x2,…xn),которая носит название целевой функции f(x) при условии, что переменные х принадлежат некоторой области G.

В зависимости от вида функций f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что:

а)функция f(x) является линейной функцией переменных х1,х2,..хn;

б) область G определяется системой линейных равенств или неравенств;

Математическая модель любой задачи линейного программирования включает в себя:

-максимум или минимум целевой функции (критерий оптимальности);

-систему ограничений в форме линейных уравнений и неравенств;

-требование неотрицательности переменных.

Планирование деятельности с использованием методов

линейного программирования.⁴

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

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

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

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

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

Постановку задачи методом линейного программирования можно представить следующим образом:

Имеются какие-то переменные x=(x1,x2,….,xn) и целевая функция этих переменных f(x)=(x1,x2,….,xn). Ставится задача: найти максимум или минимум целевой функции f(x) при условии, что переменные x принадлежат некоторой области, которая имеет ограничения.

Линейное программирование включает в себя ряд шагов:

1. Идентифицировать управляемые переменные и цель задачи.

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

3. Рассмотреть все допустимые сочетания переменных. Как правило, исследование задачи базируется на использовании пакетов прикладных программ.

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

- задача о перевозках (транспортная задача)

- задача на распределение сил и средств (распределение сил и средств поражения по целям, распределение сил и средств разведки и др.)⁵

Основные теоремы линейного программирования:

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

Однако сначала напомним о некоторых важных понятиях.

Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными (или свободными).

Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

Теорема 2. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.

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

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

Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений.

Таким образом, оптимальное решение ЗЛП следует искать среди конечного числа допустимых базисных решений.⁶

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

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

Построить двойственную задачу можно по следующим правилам:

Количество переменных в двойственной задаче равно количеству неравенств в исходной.

Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

Столбец свободных членов исходной является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

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

Транспонированной называется матрица, у которой строки и столбцы меняются местами. Поэтому коэффициенты при переменных y_i в задаче II это, соответственно, коэффициенты i-ого неравенства в задаче I. Неравенства, находящиеся напротив друг друга, называются сопряженными .

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

Теорема 1 (первая теорема двойственности)

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*)=G(y*), где х*, у* - оптимальные решения задачи I и II

Теорема 2 (вторая теорема двойственности)

Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задачи I и II соответственно, хотя бы одно из любой пары сопряженных неравенств обращается в равенство.⁷