Специальные задачи линейного программирования

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

• Введение
• Обзор литературы
• 1. Целочисленное программирование
• 2. Методы ветвей и границ
• 3. Задача выбора вариантов
• 4. Дискретное программирование
• 5. Методы решения дискретных задач
• Заключение
• Список используемой литературы
• Введение
• Переход к рыночной экономике и функционированию рыночного механизма регулирования включает в себя совершенствование этапа планирования, который становится тесно связанным с прогнозированием эффективных направлений экономического развития. Актуальными являются разработка математического описания экономических процессов и развитие методов оптимизации для решения возникающих сложных математических задач. Это особенно существенно для определения вариантов экономического развития на перспективу, когда необходимо учитывать крупные и продолжительные народнохозяйственные мероприятия: создание и развитие территориально-производственных комплексов, обеспечение скоординированных программ исследований и разработок, распределение ресурсов для выполнения отдельных комплексов работ при программно-целевом планировании, осуществление выпуска крупных изделий, производство которых требует значительного времени.
• Традиционный путь решения линейных динамических целочисленных задач состоит во введении дискретного времени, получении в результате этого линейных алгебраических соотношений и применении описанных в литературе общих или специализированных методов целочисленного линейного программирования (ЦЛП).
• Оптимальное решение является наилучшим только в рамках использования данной модели. Не следует считать, что это действительно самое лучшее решение анализируемой задачи.
• Целью данной работы является обзор и анализ методов решения специальных задач линейного программирования.
• Обзор литературы
• При написании курсовой работы мною была использована книга «Математические методы и модели для менеджмента» (Глухов В. В., Медников М. Д., Коробко С. Б.), имеющаяся в библиотеке колледжа. Именно в ней наиболее полно изложен материал о специальных задачах линейного программирования. Так же в издании имеется достаточное количество схем и примеров для структурирования прочитанной информации.
• Вторым, но не менее важным источником, служит книга «Методы оптимизации» (Харчистов Б.Ф.). В ней изложены основные понятия и теоретические положения курса "Методы оптимизации". Приведены алгоритмы, реализующие различные методы решения оптимизационных задач.
• 1. Целочисленное программирование
• Первые упоминания о линейных уравнениях возникли еще за несколько веков до нашей эры.
• В Древней Греции Диофант (II-III вв.) формулирует уравнения, в которых искомые переменные -- целые. Например, для уравнения первой степени, а₀ + a₁x₁ = 0, где a₀, a₁ -- целые, решение x₁ = -a₀/a₁ -- целое, если a₀ делится на a₁ без остатка, т. е. такое уравнение не всегда разрешимо в целых числах. Из двух уравнений 3x₁ - 27 = 0 и 5x₂ + 21 = 0 только первое имеет целое решение: x₁ = 27/3 = 9, а второе -- нет, так как x₂ = -21/5.
• Для уравнения с двумя неизвестными: a₁x₁ + a₂x₂ = 0, где a₂, a₁ -- целые, решение будет x₁ = -(a₂/a₁)x₂. Например,
• 10x₂ - 5x₂ = 0 или x₁ = 0,5x_2. (1)
• Из этого примера можно сделать следующие выводы: уравнение имеет бесчисленное множество решений, так как n > m; решение -- целое, если x₂ -- четное.
• Для того чтобы из множества допустимых решений выбрать одно -- оптимальное, необходимо, как нам уже известно, добавить к условию (1) целевую функцию. Задачи оптимизации, в которых решение должно быть в целых числах, называют задачами целочисленного программирования. Если в этой задаче целевая функция и ограничения -- линейные зависимости, то ее называют целочисленной задачей линейного программирования; если же хотя бы одна зависимость будет нелинейной, то такая задача формулируется как целочисленная нелинейного программирования.
• Большинство практических задач принятия решения сводится к целочисленным задачам линейного программирования.
• Если к условию (1) добавить такие, например, граничные условия:
• 2 ? x₁ ? 8; 1 ? x₂ ? 3
• то можно видеть, что такая система решения не имеет. Отсюда следует, что задача целочисленного программирования не всегда имеет решение, т. е. она не совместна.
• Под целочисленным или дискретным программированием понимают такие задачи (обычно линейные), в которых искомые переменные по смыслу могут принимать только целые значения: число рабочих, разделяемых по рабочим местам; количество единиц оборудования, устанавливаемых на заданной площади, и т. п.
• Аналитическая задача целочисленного программирования формулируется:
• max(min) L =
• Если n₁ = n, то задачу называют полностью целочисленной; если n₁ < n, то -- частично целочисленной.
• Предположим, что задача имеет многогранник решений (рис. 1). Если наложить требование целочисленности, то допустимое множество решений выразится в систему точек и уже не будет выпуклым.

• Если добавить новые ограничения, связывающие внешние целочисленные точки, а затем в качестве многогранника использовать все выпуклое множество, ограниченное осями координат и новым контуром, то получим новую задачу линейного программирования со следующими свойствами:
• ¦ новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка целая;
• ¦ так как целевая функция достигает оптимума в угловой точке, то построением многогранника обеспечивается целочисленность оптимального решения.
• Таким образом, решение задач целочисленного программирования трудоемко. Поэтому по возможности лучше не накладывать ограничений целочисленности переменных.
• В ряде случаев задачу целочисленного программирования решают следующим образом:
• 1) как непрерывную задачу линейного программирования;
• 2) округляют переменные;
• 3) проверяют допустимость округленного решения;
• 4) если решение допустимое, то оно принимается как целочисленное.
• При необходимости точного решения применяют специальные методы, где учитывается, что множество решений любой целочисленной задачи -- конечно. Например, в задаче с переменными x₁, x₂: 0 < x₁ ? 4; 0 < x_j ? 5. Число возможных решений 4*5 = 20. Следовательно, возможен полный перебор всех возможных сочетаний целочисленных x₁, x₂ и выбор из них наилучших в смысле целевой функции. Трудоемкость этого метода возрастает с ростом числа переменных и области граничных условий, и для реальных задач он неприменим.
• Поэтому в реальных задачах применяют методы, в которых не рассматривают все возможные альтернативы. Распространены методы отсечений и методы возврата, среди которых наиболее известен метод ветвей и границ. Метод отсечений для программной реализации сложен.
• Решение задачи методом Гомори
• Во многих экономических задачах переменные выражают физически неделимые объекты и потому могут принимать только натуральные значения. Соответственно, в таких задачах на переменные накладывается дополнительное требование их целочисленности.
• (1.1)
• Присоединяя равенство (1.1) к ранее решенной задаче, получить новую задачу линейного программирования, которую вновь решить симплексным методом. Если ее оптимальное решение окажется целочисленным, то оно и будет оптимальным решением исходной задачи. Если снова получится нецелочисленное решение, то построить новое сечение, и т.д.
• Пример. Найти наибольшее значение функции
• при ограничениях:

• 2. Метод ветвей и границ
• Задача линейного программирования решается без учета целочисленности. Такая задача называется непрерывной. Далее рассматривают одну из переменных x_j, на которую накладывают ограничение целочисленности, но которая получила дробное значение. На основе полученного решения составляют дополнительные ограничения:
• x_j ? [] и x_j ? [] + 1,
• где [] -- целая часть нецелочисленного значения переменной в оптимальном решении, и затем решаются еще две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных.
• Полученное решение новых задач проверяют на целочисленность переменных. Если решение не удовлетворяет требованию целочисленности, на основе каждой из задач составляют, аналогично предыдущим, две новые и т. д.
• Если одно из решений удовлетворяет требованию целочисленности, значение целевой функции принимается за граничное L_гр. При этом рассмотрение других задач продолжается до тех нор, пока не будет получено:
• ¦ на одной из ветвей недопустимое решение;
• ¦ на одной из ветвей целочисленное решение. Тогда значение целевой функции сравнивается с L_гр (верхним - при max, нижним - при min); если полученное значение хуже, оно отбрасывается; если лучше, то принимается за граничное;
• ¦ на одной из ветвей нецелочнеленное решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается. На первом цикле расчета
• Таким образом, для получения целочисленного решения методом ветвей и границ приходится решать большое число задач линейного программирования, причем в каждом очередном ветвлении число ограничений увеличивается на 1. Поэтому время решения задачи целочисленного программирования по сравнению с непрерывной значительно увеличивается.
• Пример 1.
• max L = 7x₁ + 3x₂,
• Решение. В результате решения задачи симплекс-методом найдем оптимальное решение = 1; = 7,5; L₁ = 29,5, где верхний индекс переменных -- номер задачи.
• В полученном решении x₂ = 7,5 -- нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.
• Задача 2. Задача 3.
• max L = 7x₁ + 3x₂, max L = 7x₁ + 3x₂,
• 
• Результаты решения симплекс методом задачи 2: = 1,2; = 7; L₂ = 29,4; задачи 3: = 0,75; = 8; L₃ = 29,25;
• В задаче 1 переменная = 1 -- целочисленная, а в последующих задачах при целочисленности х₂ перестала быть целочисленной x₁. Затем следует накладывать ограничения целочисленности на x₁ и т. д. (рис. 2).
• Результаты решения непрерывной и целочисленной задачи вводятся в таблице 1. В качестве оптимального принимается решение задачи 5, которое дает наибольшее из целочисленных решений значение целевой функции.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

• Таблица 1.

N задачи	X1	X2	L	N задачи	X1	X2	L
1	1	7,5	29,5	5	2	5	29
4	1	7	28	6	0	9	27

• Из примера видно, что метод ветвей и границ достаточно трудоемкий. При этом оптимальное решение может быть получено в результате сравнения всех допустимых целочисленных решений. Поэтому при решении задач реальной размерности может потребоваться память, которой нет даже в современных компьютерах, или потребуется практически неприемлемое время решения.
• Обязательное условие метода -- наличие верхних границ на значения переменных D_j. Если D_j не назначена, то ее определяют по зависимости:
• Где минимальные значения всех , для которых определяется верхняя граница .
• 3. Задача выбора вариантов
• Перейдем теперь к частному случаю задач целочисленного программирования -- задаче выбора вариантов.
• В этом частном случае искомая переменная , в результате решения может принимать не любое целое значение, а только одно из двух: либо 0, либо 1. Чтобы такие переменные отличать от обычных и каждый раз не писать [0; 1], будем их вместо , обозначать . И это уже будет означать, что в результате решения задачи может быть равным или 0 или 1, т. е. всегда Такие переменные обычно называют булевыми (в честь предложившего их английского математика Джорджа Буля, 1815-1864).
• С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо что-то выбирать из имеющихся различных вариантов (например, еще в первобытнообщинном строе глава племени наверняка решал такую задачу, выбирая, какого члена общины на какую работу поставить), в том числе: задачи о назначении, выбора вариантов, дискретного программирования.
• Пример 2. В задаче выбора вариантов примем, что для получения результата в виде максимально возможной прибыли необходимы два видя ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли (табл. 2).
• Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех (k 3).
• Решение. Для составления модели примем, что j-му варианту будет соответствовать (j - 1, …, 4). При этом
• Тогда математическая модель задачи запишется:
• max L = 65 + 80 + + 210,
• Таблица 2.

Показатели	Варианты	Наличие
	1	2	3	4
Прибыль, д. е./ед.	65	80	90	210	_
Материальные ресурсы	200	180	240	250	800
Трудовые ресурсы	10	15	22	28	50

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

Из результатов решения этой задачи (первый столбец табл. 3) видна, что наибольшая прибыль (max L = 300) будет получена в том случае, если будут приняты третий и четвертый варианты.

Таблица 3.

Оптимальное решение	Дополнительные условия
	нет	=	+ = 1
	0	0	1
	0	1	1
	0	0	1
	1	1	0
Прибыль (max L)	300	290	235

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

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

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

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

Max L =

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

Если накладывается требование «должен», то в ограничении ставится знак равенства: (число принятых вариантов «должно быть» три).

Если требование «может», то -- знак неравенства, в частности:

¦ если накладывается требование «И», то

например, принятие и первого и третьего вариантов запишется ;

¦ если для вариантов накладывается требование «ИЛИ», то условие запишется:

Следовательно, если принять, что соответствует «быть», -- «не быть», то извечный вопрос «быть или не быть» запишется + = 1. В этом случае есть два допустимых решения: = 1,= 0 означает «быть»; = 0, = 1 -- означает «не быть». Так как целевая функция не сформулирована, то дать оптимальный ответ на этот вопрос невозможно. Чтобы принять решение, необходимо знать, чего мы хотим. Но об этом мы уже неоднократно говорили.

4. Дискретное программирование

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

Пример 3. Мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить спинок диванов, подлокотников кресел и ножек стульев при известном удельном расходе ресурсов (табл. 4)., чтобы доход был максимальным.

Таблица 4.

	Изделия	Наличие ресурса
Показатели	спинка дивана	подлокотники кресла	ножка стула
Цена, д. е./ед.	20	6	8	--
Древесина	10	5	3	206
Трудозатраты	2	7	4	100
Спрос	10	8	12	--
	x1	x2	x3

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

 L =

10,

10,

10,

где - варианты количества подлокотников и ножек (k = 1, …, k_i).

Здесь дополнительное введение булевых переменных дает возможность обеспечить выпуск изделий в кратном заданном количестве. Так, для подлокотников x₂ может принимать следующие значения: если в результате решения будет получено , а остальные то x₂; если , а остальные , то x₂ = 4 и т.д.

Для решения задачи с учетом дополнительных условий мы ввели еще семь переменных и четыре ограничения. Следовательно, введение дополнительных требований привело к увеличению размерности задачи. Заметим, что если бы нам требовалось определить выпуск спинок, подлокотников и ножек для одного изделия (комплекта), то можно было бы записать x₂ = 2х₁; х₃ = 4x₁ и не вводить дополни тельных ограничений и булевых переменных. Но это была бы другая задача.

В результате решения задачи были получены следующие значения: max L = 320; = 1; = 4; = 12; 0;

При этом оказались не полностью использованы ресурсы: резерв первого равен 50, второго -- 4 ед.

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

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

max(min)

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

max(min)

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

5. Методы решения дискретных задач

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

Есть три метода решения задач с булевыми переменными:

¦ метод ветвей и границ;

¦ метод сплошного перебора;

¦ метод фильтрующего ограничения.

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

Совершенно очевидно, что выполнение этих двух требований обеспечивает получение в решении значений [0; 1] т. е. равных 0 или 1.

Пример 4. Требуется решить систему методом сплошного перебора:

max L = 3₁ - 2₂ + 5₃

Решение. Так как ₁, ₂, ₃ могут принимать значения 0 или 1 в любом сочетании, рассмотрим все возможные сочетания (табл. 5) в следующей последовательности.

Таблица 5.

№ варианта	1	2	3	(1)	(2)	(3)	(4)	L
1	0	0	0	0	0	0	0	0
2	1	0	0	1	1	1	4	3
3	0	1	0	2	4	1	0	-2
4	0	0	1	-2	1	0	1	5
5	1	0	1	0	2	1	5	8
6	1	1	0	3	5	2	4	1
Требование				<2	<4	<3	<6	max

1. Заполнить все возможные сочетания допустимых значений ₁, ₂, ₃.

2. Определить и записать значения левых частей ограничений (1)-(4) и целевой функции.

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

4. Из оставшихся вариантов принимается тот, в котором целевая функция максимальна. В примере max L = 8 -- в шестом варианте (оптимальном), в котором = = 1; .

Из этого примера видно, что в данном случае всего вариантов будет 2³ = 8 и для каждого варианта надо вычислить четыре ограничения и целевую функцию, т. е. выполнить N = 8(4 + 1) = 40 вычислительных операции. Значит, в общем случае N = 2ⁿ(m + 1), где n -- число переменных, m - число ограничений. Следовательно, при увеличении размерности задачи число вычислений резко возрастает (табл. 6).

Таблица 6.

n	ТО
	4	10	15
3	40	88	120
5	160	352	512
10	5120	11264	16384

Для сокращения трудоемкости полного перебора применяют различные методы.

Метод фильтрующего ограничения предполагает следующую последовательность действий.

1. Принимают некоторые значения ₁, ₂, ₃, например: 1, 0, 0.

2. Определяют значение целевой функции при таком на боре переменных L = 3₁ - 2₂ + 5₃ = 3*1 - 2*0 + 5*0 = 3.

3. Далее устанавливают новые значения переменных и целевой функции; причем если полученная целевая функция меньше 3, то этот вариант не рассматривают. Дли исключения возможного рассмотрения такого варианта, вводят дополнительное ограничение 3₁ - 2₂ + 5₃ ? 3, которое называют фильтром (Ф).

4. Составляют таблицу (табл. 7), в которой для каждого варианта проверяют выполнение всех ограничений, включая Ф.

Если вычисление прекращается и величины не определены, то в клетках таблицы ставится прочерк.

Введение фильтрующего ограничения Ф привело к сокращению числа вычисляемых величин (24 вместо 40, т. е. 60%).

№ варианта	1	2	3	F = Ф	(1)	(2)	(3)	(4)
1	0	0	0	-	-	-	-	-
2	1	0	0	3	1	1	1	4
3	0	1	0	-2	-	-	-	-
4	1	1	0	1	-	-	-	-
5	0	0	1	5	-1	1	0	1
6	1	0	1	8	0	2	1	5
7	0	1	1	3	1	5	-	-
8	1	1	1	6	2	6	-	-
Требование				> 3	< 2	< 4	< 3	< 6

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

Например, из таблицы видно, что в пятом варианте Ф = 5. Поэтому для дальнейших вычислений в качестве фильтрующего ограничения принимаем 3₁ - 2₂ + 5₃ ? 5 (Ф₁). Однако для следующего варианта значение целевой функции будет еще больше (Ф = 8) и в качестве фильтрующего ограничения принимается 3₁ - 2₂ + 5₃ ? 8 (Ф₂). Для седьмого и восьмого вариантов значение целевой функции не удовлетворяет требованиям фильтра Ф₂ и значения ограничений не вычисляем. Значит, трехкратный фильтр (Ф, Ф₁, Ф₂) позволил сократить вычисления еще на 4, т. е. надо выполнить 20 вычислений вместо 40 (50%). Более значительное сокращение трудоемкости достигается методом Беллмана с фильтром, где наибольший Ф получают сразу.

Заключение

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

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

Список используемой литературы

математический модель дискретный целочисленный оптимизация

1. Глухов В. В., Медников М. Д., Коробко С. Б. Математические методы и модели для менеджмента.2-е изд., испр. и доп. - СПб.: Издательство «Лань», 2005. - 5 с. - (Учебники для вузов. Специальная литература).

2. «Исследование операций в экономике»: Учебное пособие для вузов / Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н.: под ред. проф. Кремера Н. Ш. - М.: ЮНИТИ, 2004

3. Харчистов Б.Ф. Методы оптимизации: Учебное пособие. - Таганрог: Изд-вo ТРТУ, 2004. - 140с.

4. «Линейное и нелинейное программирование» под общей редакцией профессора Ляшенко И. Н., Киев - 1975

5. «Математические методы и модели в коммерческой деятельности»: Учебник, 2-е изд., перераб. и дополн. / Фомин Г. П. - М: Финансы и статистика, 2005

6. «Математические методы и модели исследования операций»: Учебное пособие / Кутузов А. Л. - издательство СПб ГПУ, 2005

7. «Математические методы: Учебник» / Партика Т. Л., Попов И. И. - М: ФОРУМ: ИНФРА, 2005

Размещено на Allbest.ru