Методы линейного программирования. Симплексный метод решения задач линейного программирования
Линейное программирование - один из важнейших разделов математики, изучающий теории и методы решения определенных задач. Эта математическая дисциплина стала в последние годы широко применяться в различных областях экономики, техники и военного дела, где в их развитии не последнюю роль играет математическое планирование и использование автоматических цифровых вычислительных машин. Данный раздел науки изучает линейные оптимизационные модели. Иначе говоря, линейное программирование посвящено чис
Впервые термин "линейное программирование" предложил американский экономист Т.Купманс в 1951 году. В 1975 году. русский математик Л.В.Канторович и Т.Купманс были удостоены Нобелевской премии по экономическим наукам за свой вклад в теорию оптимального распределения ресурсов. Т.Купманс пропагандировал методы линейного программирования и защищал приоритеты Л.В.Канторовича, открывшего эти методы.
История линейного программирования в США уходит корнями в 1947 год, когда Дж.Данциг написал об этом в своей работе. Л.В.Канторович изучал возможность применения математики к вопросам планирования, на основе чего в 1939 году была опубликована его монография "Математические методы организации и планирования производства". Важнейшей находкой (открытием) Л.В.Канторовича явилась возможность четко математически сформулировать важнейшие производственные задачи, что позволяет найти количественный подход к данным задачам, а также их решение численными методами.
Если бы первые работы Л.В.Канторовича получили в свое время должную оценку, то была бы велика вероятность еще большего продвижения линейного программирования в настоящее время. К сожалению, его работа оставалась в тени как в Советском Союзе, так и за его пределами, и, как отмечает Данциг: " ...и за это время линейное программирование стало настоящим искусством."
Оптимальный план любой линейной программы следует автоматически связывать с оптимальными ценами или, согласно Л.В.Канторовичу, с "объективно обусловленными оценками". Это нагромождение слов имело целью повысить "критикоустойчивость" термина. Суть экономического открытия Л.В.Канторовича заключается во взаимосвязи оптимальных решений и оптимальных цен.
Методы линейного программирования
С помощью методов линейного программирования решается большое количество экстремальных задач, связанных с экономикой. В этих случаях находят крайние значения (максимум и минимум) некоторых функций переменных величин.
Основой линейного программирования служит решение системы линейных уравнений, которые преобразуются в уравнения и неравенства. Оно характеризуется математическим выражением переменных величин, определенным порядком, последовательностью расчетов, логическим анализом. Оно применимо:
- при наличии математической определенности и количественной ограниченности между изучаемыми переменными величинами и факторами;
- при взаимозаменяемости факторов из-за последовательности расчетов;
- в случае совмещения математической логики с пониманием сущности изучаемых явлений.
В промышленном производстве этот метод помогает исчислению оптимальной общей производительности машин, агрегатов, поточных линий (в случае, если задан ассортимент продукции и соответствующие величины), а также решению задачи рационального использования материалов (с наиболее выгодным количеством заготовок).
В сельском хозяйстве с помощью этого метода определяют минимальную стоимость кормовых рационов с учетом заданного количества кормов (исходя из видов и содержащихся в них полезных веществ).
В литейном производстве данный метод помогает решить задачу о смесях, входящих в состав металлургической шихты. Этот же метод позволяет решить транспортную задачу, задачу наиболее оптимального прикрепления потребляющих предприятий к предприятиям, производящим продукцию.
Отличительной особенностью всех экономических задач, которые можно решить, применяя методы линейного программирования, является выбор вариантов решения, а также определенные ограничивающие условия. Решение подобной задачи означает выбор наиболее оптимального из всех альтернативных вариантов.
Существенной ценностью применения методов линейного программирования в экономике является выбор наиболее оптимального варианта из огромного количества всех допустимо возможных вариантов. Иными способами почти невозможно решать подобные задачи, чтобы найти степень рациональности использования ресурсов в производстве.
Одной из основных задач, решаемых с помощью линейного программирования, является транспортная задача, которая имеет целью минимизировать грузооборот товаров широкого потребления при их доставке от производителя к потребителю.
Линейное программирование
Линейное программирование - математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства , задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования . Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования . Одним из обобщений линейного программирования является дробно-линейное программирование .
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
История
Метод внутренних точек был впервые упомянут И. И. Дикиным в 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 .
- Зальтен, Феликс
- Глагов, Мартина
Смотреть что такое "Линейное программирование" в других словарях:
линейное программирование - — линейное программирование Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между… … Справочник технического переводчика
Линейное программирование
Линейное программирование - область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… … Экономико-математический словарь
Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин.
Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Для него характерны математическое выражение переменных величин, определенный порядок, последовательность расчетов (алгоритм), логический анализ. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика совмещаются с логически обоснованным пониманием сущности изучаемого явления.
С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий (при заданном ассортименте продукции и иных заданных величинах), решается задача рационального раскроя материалов (с оптимальным выходом заготовок). В сельском хозяйстве он используется для определения минимальной стоимости кормовых рационов при заданном количестве кормов (по видам и содержащимся в них питательным веществам). Задача о смесях может найти применение и в литейном производстве (состав металлургической шихты). Этим же методом решаются транспортная задача, задача рационального прикрепления предприятий-потребителей к предприятиям-производителям.
Все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями. Решить такую задачу - значит выбрать из всех допустимо возможных (альтернативных) вариантов лучший, Оптимальный. Важность и ценность использования в экономике метода линейного программирования состоят в том, что оптимальный вариант выбирается из весьма значительного количества альтернативных вариантов. При помощи других способов решать такие задачи практически невозможно.
В качестве примера рассмотрим решение задачи рациональности использования времени работы производственного оборудования.
В соответствии с оперативным планом участок шлифовки за первую неделю декабря выпустил 500 колец для подшипников типа А, 300 колец для подшипников типа Б и 450 колец для подшипников типа В. Все кольца шлифовались на двух взаимозаменяемых станках разной производительности. Машинное время каждого станка составляет 5000 мин. Трудоемкость операций (в минутах на одно кольцо) при изготовлении различных колец характеризуется следующими данными (табл. 6.5).
Таблица 6.5
Следует определить оптимальный вариант распределения операций по станкам и время, которое было бы затрачено при этом оптимальном варианте. Задачу выполним симплексным методом.
Для составления математической модели данной задачи введем следующие условные обозначения: jc, х2, хъ, - соответственно количество колец для подшипников типов Л, Б, В, производимых на станке I; х4, х5, х6, - соответственно количество колец для подшипников типов А, Б, В, производимых на станке II.
Линейная форма, отражающая критерий оптимальности, будет иметь вид:
min а(х) = 4x,-f 10x2-f 10x3-f 6x4-f 8х5+20х6 при ограничениях
4х, -f 10х2 -f 10;t3 lt; 5000
6х4 -f 8х5 -f 20х6 ~lt; 5000
х, = 500
х2 +х5 = 300
х3 +х6 = 450
Xj^0,j=l, ..., 6
Преобразуем условие задачи введением дополнительных (вспомогательных) и фиктивных переменных. Условие запишем так:
шіп lt;х(х) = 4дг, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Мх9 + Мх{0+Мх{,
Система уравнений, отражающая ограничительные условия машинного времени и количество произведенной продукции:
4х, + l(bc2 + 10х3 +х1 = 5000
6х4 + 8х5 + 20х6 + xs = 5000
Xj +х4 +х9 = 500
х2 +х5 +х10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Решение этой задачи представлено в табл. 6.6. Оптимальный вариант получен на седьмом этапе (итерации). Если бы на станке I производилось 125 колец подшипников типа А, 450 колец подшипников типа В, на станке II - 375 колец подшипников типа А и 300 колец подшипников типа Б, то при такой загрузке оборудования было бы высвобождено 350 мин машинного времени станка II. Общие затраты времени по оптимальному варианту составили бы 9650 мин, тогда как фактически затрачено 10000 мин машинного времени.
Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Ее смысл заключается в минимизации грузооборота при доставке товаров широкого потребления от производителя к потребителю, с оптовых складов и баз в розничные торговые предприятия. Она решается симплекс-методом или распределительным методом.
Решение транспортной задачи распределительным методом было дано в третьем издании учебника «Теория экономического анализа» («Финансы и статистика», 1996).
Решение задачи рациональности использования станков симплексным методом
| Базис | с | Ро | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | м | м | м |
| Л | Рг | Ръ | Л | Р ъ | | Pi | Р8 | р* | Л 0 | Л, |
|||
| Л | 0 | 5000 | 4 | 10 | 0 | 0 | 0 | 0 | і | 0 | 0 | 0 | 0 |
| Р, | 0 | 5000 | 0 | 0 | 0 | 6 | 8 | 20 | 0 | 1 | 0 | 0 | 0 |
| Л | м | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Л 0 | м | 300 | ш | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| Л. | м | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| Zj-Cj | | 1250М | М-4 | М-10 | М-10 | М-6 | М-8 | М-20 | 0 | 0 | 0 | 0 | 0 |
| Pi | 0 | 3000 | 0 | 10 | 10 | -4 | 0 | 0 | 0 | 0 | -4 | 0 | 0 |
| р* | 0 | 5000 | 0 | 0 | 0 | 6 | 8 | 20 | 1 | 1 | 0 | 0 | 0 |
| Ро | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Ло | м | 300 | 0 | 1 | 0 | 0 | ш | 0 | 0 | 0 | 0 | 1 | 0 |
| Л. | м | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| zr-9 | | 750Л/+2000 | 0 | М-10 | М-10 | -2 | М-8 | О 2 | 0 | 0 | -М + 4 | 0 | 0 |
| Базис | С | Р0 | 4 | Pi | 10 | 6 | 8 | 20 | 0 | 0 | м | м | М |
| | | Pi | 10 | ^3 | л | Р5 | р6 | Pi | р« | р9 | Pi 0 | Рц |
|
| Pi | 0 | 3000 | 0 | 10 | 10 | -4 | 0 | 0 | 1 | 0 | -4 | 0 | 0 |
| Р* | 0 | 2600 | 0 | -8 | 0 | 6 | 0 | 20 | 0 | 1 | 0 | -8 | 0 |
| Pi | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Р5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| РП | М | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| Zj-Cj | | 450Л/+4400 | 0 | -2 | М-10 | -2 | 0 | М-20 | 0 | 0 | -М+4 | -М+8 | 0 |
| Ръ | 10 | 300 | 0 | 1 | 1 | 4 10 | 0 | 0 | 1 10 | 0 | 4 10 | 0 | 0 |
| Р% | 0 | 2600 | 0 | -8 | 0 | 6 | 0 | 20 | 0 | 1 | 0 | -8 | 0 |
| Pi | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Р5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| Рц | М | 150 | 0 | -1 | 0 | j4_ 10 | 0 | 1 | _ J_ 10 | 0 | 4 10 | 0 | 1 |
| zrCj | | 150Л/+7400 | 0 | -M+S | 0 | - М-6 10 | 0 | М-20 | - ~М+1 10 | 0 | -±м 10 | - Af+8" | 0 |
| Базис | с | Л, | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | М | М | м |
||
| Л | Рг | Л | л | PS | р6 | Pi | рamp; | Р9 | Ло | л. |
|||||
| Л | 10 | 300 | 0 | 1 | 1 | 4 | 0 | 0 | 1 | | 0 | | 4 | 0 | 0 |
| | | | | | | “10 | | | То | | | | “ 10 | | |
| р6 | 20 | 130 | 0 | 4 | 0 | 3 | 0 | 1 | 0 | | 1 | | 0 | 4 | 0 |
| | | | | ~Ї0 | | 10 | | | | | 20 | | | 10 | |
| л | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | 0 | | 1 | 0 | 0 |
| Ps | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | 0 | | 0 | 1 | 0 |
| Р\\ | М | 20 | 0 | 6 | 0 | 1 | 0 | 0 | 1 | | 1 | | 4 | 4 | 1 |
| | | | | 10 | | ~10 | | | То | | 20 | То | 10 | |
|
| Zj-Cj | | 20М+10000 | 0 | | 0 | -м | 0 | 0 | м+\ | | -м+\ | --М | -*М | 0 |
|
| | | | | 10 | | 10 | | | 10 | 20 | | 10 | 10 | |
|
| л | 10 | 380 | 0 | 14 | 1 | 0 | 0 | 0 | 3 | | 2 | | 12 | 0 | 0 |
| | | | | 10 | | | | | 10 | | 10 | 10 | | |
|
| р% | 20 | 70 | 0 | 14 | 0 | 0 | 0 | 1 | 3 | | 2 | | 12 | 16 | -3 |
| | | | | 10 | | | | | 10 | | 10 | | 10 | 10 | |
| Л | 4 | 300 | 1 | 6 | 0 | 0 | 0 | 0 | 1 | | 1 | | -3 | | -10 |
| | | | | | | | | | | | 2 | | | | |
| р5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | 0 | | 0 | 1 | 0 |
| Р4 | 6 | 200 | 0 | -6 | 0 | 1 | 0 | 0 | -1 | | 1 | | 4 | 4 | 10 |
| | | | | | | | | | | | ’ 2 | | | | |
| Z.-Ci | | 10000 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | -М | -М | -м |
||
| Базис | | Лgt; | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | м | м | л/ |
| о | Л | Рг | ръ | Р* | Р5 | Р6 | Л | Рamp; | р9 | Л 0 | л. |
||
| Рг | 10 | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | | |
| Р% | 0 | 350 | 0 | 7 | 0 | 0 | 0 | 5 | 3 5 | 1 | | | |
| Л | 4 | 125 | 1 | 5 2 | 0 | 0 | 0 | 5 2 | 1 4 | 0 | | | |
| Ps | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | | |
| Р4 | 6 | 375 | 0 | 5 2 | 0 | 1 | 0 | 5 2 | 1 4 | 0 | | | |
| Zj-Cj | | 9650 | 0 | -7 | 0 | 0 | 0 | -5 | 1 2 | 0 | | | |
В связи с развитием техники, ростом промышленного производства все большую роль играют задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование -- формальное описание изучаемого явления и исследование с помощью математического аппарата.
Всякая модель реального процесса предполагает идеализацию и абстракцию, но они не должны уходить слишком далеко от содержания задачи, чтобы построенная модель не утратила существенных черт моделируемого объекта, т. е. была ему адекватна. С другой стороны, если построить сложную модель, учитывающую все тончайшие особенности изучаемого процесса, то это может нарушить смысл моделирования, одна из целей которого -- упростить постановку задачи, чтобы легче было ее исследовать (слишком сложная модель, как правило, не поддается анализу).
В большом числе случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важная и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной -- происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями. Сказанным определяется важность той роли, которую играет линейное программирование -- метод отыскания условного экстремума линейной функции на множестве, заданном при помощи линейных соотношений типа равенств и неравенств (линейных ограничений) .
Условия применимости линейной модели
Делимость. Если способ применяется с интенсивностями a и b (a < b), то его можно применять с любой интенсивностью x .
Это условие не тривиально. Если, например, интенсивность выполнения работы измерять числом назначенных на нее работников, то допустимы только целые значения интенсивности. Если же интенсивность измеряется числом человеко-часов в сутки, то принцип делимости, по-видимому, выполнен.
Пропорциональность. Затраты, выпуски и полезность, производимые каждым способом, пропорциональны его интенсивности.
Это условие постоянной отдачи (во всех смыслах), отсутствия эффекта масштаба. Особое внимание следует уделять выявлению диапазона интенсивности технологического способа, в котором этот способ удовлетворяет условию пропорциональности. Например, если сварщик проваривает контейнер за 6 часов, то двое сварщиков, пожалуй, справятся с этой работой за 3 часа. Но шестеро - за час - не сварят контейнер.
Аддитивность. Полезности и -- для каждого ингредиента -- затраты и выпуски, производимые всеми способами, суммируются.
Принцип аддитивности требует аккуратного и согласованного описания входящей в модель номенклатуры: технологических способов, ингредиентов, полезностей.
Формы записи задач линейного программирования
В самом общем виде задача ЛП записывается следующим образом:
- 2 (2)
- 3 (3)
- 4 (4)
- 5 (5)
Определение 1. Матрица называется матрицей задачи (1) - (5). ?
Более унифицированное представление задачи ЛП -- стандартная форма:
для i {1,…, m}, x 0.
Особенности стандартной формы: все переменные неотрицательны (n1 = n), ограничения-равенства отсутствуют (m1 = 0). Если ЦФ максимизируется, то m2 = 0 и нет ограничений вида (3); в противном случае m2 = m и нет ограничений вида (4). Полагая и, стандартную форму можно записать следующим образом:
6c x max (min) при Ax () b, x 0. (6)
Но самый простой вид имеет каноническая форма записи задач ЛП.
Определение 2. Задача (1) - (4) представлена в канонической форме, если все ограничения, кроме условий неотрицательности переменных, являются равенствами (m1 = m) и все переменные неотрицательны (n1 = n). ?
Задача ЛП в канонической форме имеет, следовательно, вид
- 7c x max (min) при Ax = b, x 0. (7)
- 1.2 Основы симплекс-метода
Рассмотрим задачу ЛП в канонической форме:
- 9 (9)
- 10х 0 (10)
Пусть и -- соответственно строка i и столбец j матрицы А0. Будем считать, что строки матрицы линейно независимы.
Любую задачу ЛП можно привести к канонической форме; если задача в канонической форме разрешима, то среди ее решений есть хотя бы одна крайняя точка множества допустимых решений; крайние точки множества допустимых решений задачи ЛП в канонической форме совпадают с БДР.
Опираясь на перечисленные факты, можно представить себе следующую процедуру решения задачи. Проверим каким-либо образом, имеет ли задача решение и, если имеет, приведем ее к канонической форме. Пусть матрица А0 канонической формы имеет размерность m Ч n и ранг m. Построим все m Ч m-подматрицы матрицы А0, отбрасывая вырожденные, оставшиеся подматрицы соответствуют базисам матрицы А0. Выберем из них допустимые базисы, построим соответствующие БДР. Выберем БДР, которое доставляет максимум целевой функции.
Но такой алгоритм на практике не может быть реализован, так как число БДР экспоненциально растет с ростом размерности задачи (числа переменных и/или ограничений). Процедуру можно ускорить, если организовать ее так, чтобы в процессе перебора БДР значение ЦФ не убывало (последовательное улучшение плана). Эта исходная идея симплекс-метода, которая реализуется следующим образом.
1. 3 Симплекс-таблицы
линейный программирование симплекс оптимизация
Преобразования задачи ЛП в канонической форме, осуществляемые симплекс-методом, удобно представлять как преобразования симплекс-таблиц. Общий вид симплекс-таблицы, которая соответствует текущей итерации симплекс-метода, представляет таблица 1.
В верхней строке записаны: заголовок первого столбца, идентификаторы всех (основных, дополнительных, вспомогательных и др.) переменных задачи и заголовок последнего столбца. Следующие m строк описывают уравнения задачи в виде:
который они имеют к началу итерации. Сначала указан идентификатор базисной переменной (в текущем базисе) для соответствующего уравнения. Затем следуют коэффициенты при переменных (в том порядке, в котором переменные записаны в первой строке). Последний элемент строки -- правая часть ограничения.
Нижняя строка соответствует уравнению
12, где и. (12)
представляющему ЦФ. Переменная z играет в нем роль базисной (имеет коэффициент 1 и не входит в другие уравнения); число F -- это правая часть уравнения (12), значение ЦФ на текущем базисном решении.
Таблица 1. Общий вид симплекс-таблицы
Замечание. Таблица описывает систему уравнений (11), поэтому текущее БДР можно получить, полагая базисные переменные равными соответствующим элементам последнего столбца, а небазисные -- равными нулю. ?
На рассматриваемой итерации происходит следующее.
Если в z-строке, в столбцах, соответствующих переменным, нет отрицательных элементов, то текущее БДР оптимально и в первом столбце таблицы записаны переменные оптимального базиса. В противном случае столбец переменной xs, для которого s < 0, становится направляющим.
Если все элементы направляющего столбца неположительны, то задача неограниченна. В противном случае вычисляем отношение элементов последнего и направляющего столбцов для всех строк, имеющих положительный элемент в направляющем столбце. Строка r, для которой это отношение минимально, становится направляющей. В первом столбце следующей симплекс-таблицы переменная xs займет место переменной xj(r).
Теперь ars -- разрешающий элемент. Элементы следующей симплекс-таблицы вычисляем по формулам:
13 при при i r (13)
- 14 (14)
- 15 (15)
Рассмотрим j = j(k). Из (11) и (12) следует, что столбец j (базисный) имеет единицу в строке k и нули в остальных строках: j = 0, aij = 1 при i = k, иначе aij = 0. Пусть k r (столбец j сохраняется в новом базисе). Тогда ari = 0 и из (13), (14), (16) следует, что для всех i и. Учитывая это, сформулируем правила преобразования симплекс-таблицы при переходе к новому базису:
- · в заголовок направляющей строки ставим заголовок направляющего столбца;
- · все числа направляющей строки делим на разрешающий элемент;
- · направляющий столбец становится единичным, с единицей в направляющей строке;
- · столбцы текущего базиса с номерами, отличными от j(r), не изменяются;
- · все остальные числа таблицы (включая элементы нижней строки и последнего столбца) пересчитываем по формулам (13) - (15), (16).
Данный метод является методом целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.
Основное содержание симплексного метода заключается в следующем:- Указать способ нахождения оптимального опорного решения
- Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения
- Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или следать заключение об отсутствии оптимального решения.
Алгоритм симплексного метода решения задач линейного программирования
Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:- Привести задачу к каноническому виду
- Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
- Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
- Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
- Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения
Пример решения задачи симплексным методом
Пример 26.1Решить симплексным методом задачу:
Решение:
Приводим задачу к каноническому виду.
Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную 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).
Метод линейного программирования в экономическом анализе
Метод линейного программирования дает возможность обосновать наиболее оптимальное экономическое решение в условиях жестких ограничений, относящихся к используемым в производстве ресурсам (основные фонды, материалы, трудовые ресурсы). Применение этого метода в экономическом анализе позволяет решать задачи, связанные главным образом с планированием деятельности организации. Данный метод помогает определить оптимальные величины выпуска продукции, а также направления наиболее эффективного использования имеющихся в распоряжении организации производственных ресурсов.
При помощи этого метода осуществляется решение так называемых экстремальных задач, которое заключается в нахождении крайних значений, то есть максимума и минимума функций переменных величин.
Этот период базируется на решении системы линейных уравнений в тех случаях, когда анализируемые экономические явления связаны линейной, строго функциональной зависимостью. Метод линейного программирования используется для анализа переменных величин при наличии определенных ограничивающих факторов.
Весьма распространено решение так называемой транспортной задачи с помощью метода линейного программирования. Содержание этой задачи заключается в минимизации затрат, осуществляемых в связи с эксплуатацией транспортных средств в условиях имеющихся ограничений в отношении количества транспортных средств, их грузоподъемности, продолжительности времени их работы, при наличии необходимости обслуживания максимального количества заказчиков.
Кроме этого, данный метод находит широкое применение при решении задачи составления расписания. Эта задача состоит в таком распределении времени функционирования персонала данной организации, которое являлось бы наиболее приемлемым как для членов этого персонала, так и для клиентов организации.
Данная задача заключается в максимизации количества обслуживаемых клиентов в условиях ограничений количества имеющихся членов персонала, а также фонда рабочего времени.
Таким образом, метод линейного программирования весьма распространен в анализе размещения и использования различных видов ресурсов, а также в процессе планирования и прогнозирования деятельности организаций.
Все же математическое программирование может применяться и в отношении тех экономических явлений, зависимость между которыми не является линейной. Для этой цели могут быть использованы методы нелинейного, динамического и выпуклого программирования.
Нелинейное программирование опирается на нелинейный характер целевой функции или ограничений, либо и того и другого. Формы целевой функции и неравенств ограничений в этих условиях могут быть различными.
Нелинейное программирование применяется в экономическом анализе в частности, при установлении взаимосвязи между показателями, выражающими эффективность деятельности организации и объемом этой деятельности, структурой затрат на производство, конъюнктурой рынка, и др.
Динамическое программирование базируется на построении дерева решений. Каждый ярус этого дерева служит стадией для определения последствий предыдущего решения и для устранения малоэффективных вариантов этого решения. Таким образом, динамическое программирование имеет многошаговый, многоэтапный характер. Этот вид программирования применяется в экономическом анализе с целью поиска оптимальных вариантов развития организации как в настоящее время, так и в будущем.
Выпуклое программирование представляет собой разновидность нелинейного программирования. Этот вид программирования выражает нелинейный характер зависимости между результатами деятельности организации и осуществляемыми ей затратами. Выпуклое (иначе вогнутое) программирование анализирует выпуклые целевые функции и выпуклые системы ограничений (точки допустимых значений). Выпуклое программирование применяется в анализе хозяйственной деятельности с целью минимизации затрат, а вогнутое — с целью максимизации доходов в условиях имеющихся ограничений действия факторов, влияющих на анализируемые показатели противоположным образом. Следовательно, при рассматриваемых видах программирования выпуклые целевые функции минимизируются, а вогнутые — максимизируются.
