1 линейное программирование. Понятие линейного программирования

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

Чистые типы Существует такое понятие – «чистый психологический тип». Собственно, понятие есть, а предметов, то есть людей, идеально подходящих под это понятие, практически нет. Нет чистокровных интровертов и однозначных экстравертов. Тем более, что мы с вами договорились

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

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

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

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

История

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году .

Задачи

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

при условиях

Задача линейного программирования будет иметь канонический вид , если в основной задаче вместо первой системы неравенств имеет место система уравнений :

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

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

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

Примеры задач

Максимальное паросочетание

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

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

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

Максимальный поток

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

Возьмём в качестве переменных - количество жидкости, протекающих через -тое ребро. Тогда

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

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

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

Транспортная задача

Имеется некий однородный груз, который нужно перевести с складов на заводов. Для каждого склада известно, сколько в нём находится груза , а для каждого завода известна его потребность в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния от -го склада до -го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются - количества груза, перевезённого из -го склада на -й завод. Они удовлетворяют ограничениям:

Целевая функция имеет вид: , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица размера . Первый игрок выбирает число от 1 до , второй - от 1 до . Затем они сверяют числа и первый игрок получает очков, а второй очков ( - число, выбранное первым игроком, - вторым). Нужно найти оптимальную стратегию первого игрока.

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

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

Алгоритмы решения

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

Первый полиномиальный алгоритм , метод эллипсоидов , был предложен в 1979 году советским математиком Л. Хачияном , разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП - методов внутренней точки , первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году . Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования , разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

См. также

• Графический метод решения задачи линейного программирования

Примечания

Литература

• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М .: «Вильямс», 2006. - С. 1296. - ISBN 5-8459-0857-4
• Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. - М .: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9
• Карманов В. Г. Математическое программирование. - 3-е издание. - М .: Наука, 1986. - 288 с.
• Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Ссылки

• - Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
• Вершик А. М. «O Л. В. Канторовиче и линейном программировании »
• Большакова И. В., Кураленко М. В. «Линейное программирование. Учебно-методическое пособие к контрольной работе ».
• Барсов А. С. «Что такое линейное программирование », Популярные лекции по математике , Гостехиздат, 1959.
• М. Н. Вялый Линейные неравенства и комбинаторика . - МЦНМО , 2003.

Wikimedia Foundation . 2010 .

• Зальтен, Феликс
• Глагов, Мартина

Смотреть что такое "Линейное программирование" в других словарях:

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

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

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

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

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

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

1. Привести задачу к каноническому виду
2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример решения задачи симплексным методом

Решить симплексным методом задачу:

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Δ k = C б X k — c k

• C б = (с 1 , с 2 , ... , с m) — вектор коэффициентов целевой функции при базисных переменных
• X k = (x 1k , x 2k , ... , x mk) — вектор разложения соответствующего вектора А к по базису опорного решения
• С к — коэффициент целевой функции при переменной х к.

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

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

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

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

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

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Линейное программирование – математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах n -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

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

Линейное программирование применяется при решении следующих экономических задач:

1. Задача управления и планирования производства.

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

3. Задача определения оптимального плана перевозок груза (транспортная задача).

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

5. Задач о смесях, диете (планирование состава продукции) и т.д.

3. МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЁ ПРЕДСТАВЛЕНИЕ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ MS EXCEL.

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

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

1. Написание и проверка символической модели линейного программирования. Модель записывается на бумаге в математическом виде.

2. Создание и отладка табличной модели линейного программирования. На основе символической модели ЛП создается ее представление в Excel.

3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.

4. ИСПОЛЬЗОВАНИЕ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ .

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

Поиск решения – это надстройка, которая предназначена для оптимизации моделей при наличии ограничений. Она состоит из двух программных компонентов: программы написанной на языке Visual Basic, который транслирует представленную на рабочем письме информацию для внутреннего представления, которая используется другой программой. Вторая программа находится в памяти компьютера в виде отдельного программного модуля. Она выполняет оптимизацию и возвращает найденное решение первой программе, которая возобновляет данные на рабочем листе. С помощью ее можно найти оптимальное значение формулы, которая сохраняется в целевой ячейке. Эта процедура работает с группой ячеек, которые непосредственно связанные с формулой в целевой ячейке. Чтобы получить результат по формуле в целевой ячейке, процедура изменяет значение в ячейках, которые влияют на поиск. Для того, чтобы уменьшить множественное число значений, которые используются в модели задачи, применяют ограничение. Эти ограничения могут содержать ссылку на другие ячейки, которые влияют на поиск.

Общий алгоритм работы с надстройкой Поиск решения.

1. В меню Сервис выбрать команду Поиск решения .
2. В поле Установит целевую ячейку введите адрес ячейки, в которй находится формула, для оптимизации модели.
3. Для того, чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Максимальному значению . Для того, чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Минимальному значению . Для того, чтобы целевая ячейка приобретала значение конкретного числа, установите переключатель в положение Значение и введите соответствующее число.
4. В поле Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Изменяемые ячейки должны быть прямо или непрямо связанные с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
5. В поле Ограничения введите все ограничения, которые налагаются на поиск решения.
6. Нажмите кнопку Выполнить .
7. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение . Для возобновления входных данных установите переключатель в положение Восстановить исходные значения.
8. Для того, чтобы прервать поиск решения, нажмите клавишу Еsс . MS Excel пересчитает лист с учетом найденных значений ячеек, которые влияют на результат.

Алгоритм роботи з надбудовою Поиск решения.

5. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩИ ПРОГРАММЫ MS EXCEL.

Пример. Кондитерский цех для изготовления трех видов карамели А, В, С использует три основных вида сырья: сахар, патоку и фруктовое пюре. Нормы затрат сахара на изготовление 1кг карамели каждого вида соответственно уровни: 0,8кг; 0,5кг; 0,6кг; патоки – 04кг; 0,4кг; 0,3кг; фруктового пюре – 0кг; 0,1кг; 0,1кг. Конфеты можно производить в любых количествах (реализация обеспечена), но запас сырья ограниченный: запасы сахара – 80кг, патоки – 60кг, фруктового пюре – 12кг. Прибыль от реализации 1кг карамели вида А составляет 10грн., вида В – 11грн., вида С – 12грн.

Таблица 1

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

Линейное программирование сформировалось как отдельный раздел прикладной математики в 40 – 50-х гг. ХХ в. благодаря работам советского ученого, лауреата Нобелевской премии Л.В. Канторовича. В 1939 году им была опубликована работа «Математические методы организации и планирования производства», в которой он с использованием математики решил экономические задачи о наилучшей загрузке машин, раскрое материалов с наименьшими расходами, распределении грузов по нескольким видам транспорта и другие, предложив метод разрешающих множителей 8 .

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

Понятие линейного программирования было введено американским математиком Д. Данцигом, который в 1949 г. предложил алгоритм решения задачи линейного программирования, получивший название «симплексный метод».

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

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

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

Линейное программирование получило широкое развитие в связи с тем, что было установлено: ряд задач сферы планирования и управления может быть сформулирован в виде задач линейного программирования, для решения которых имеются эффективные методы. По оценкам специалистов примерно 80–85 % всех решаемых на практике задач оптимизации относится к задачам линейного программирования.

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

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

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

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

Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции, называемой целевой 10:

от n переменных x 1 , x 2 , …, х n при наложенных функциональных ограничениях:

(3.2)

и прямых ограничениях (требовании неотрицательности переменных)

, (3.3)

где a ij , b i , c j – заданные постоянные величины.

В системе ограничений (3.2) знаки «меньше или равно», «равно», «больше или равно» могут встречаться одновременно.

ЗЛП в более краткой записи имеет вид:

,

при ограничениях:

;

.

Вектор `Х = (x 1 , x 2 , …, х n ) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называют планом (или допустимым решением ) ЗЛП.

Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции f (`X ), называется оптимальным планом задачи и обозначается f (`X * ), где ` Х * =(x 1 * , x 2 * , …, х n * ).

Еще одна форма записи ЗЛП:

,

где f (`X * ) есть максимальное (минимальное) значение f (С , х ), взятое по всем решениям, входящим в множество возможных решений Х .

Определение 2 11 . Математическое выражение целевой функции и ее ограничений называются математической моделью экономической задачи.

Для составления математической модели необходимо:

1) обозначить переменные;

2) составить целевую функцию исходя из цели задачи;

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