Глава 2 Линейное и целочисленное программирование

Глава 2 Линейное и целочисленное программирование

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

 

Пусть дана система т линейныхуравнений и неравенств с п переменными:

 

(1)

и линейная функция:

(2)

Требуется найти решение системы при котором функция z принимает оптимальное значение (максимальное или минимальное).

Такая задача называется задачей линейного программирования (ЗЛП) в общем виде. Система (1) называется системой ограничений; функция (2) называется целевой функцией (функцией цели).

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

К их числу относятся задачи:

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

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

- оптимизации производственной программы предприятий;

- оптимального размещения и концентрации производства;

- на составление оптимального плана перевозок, работы транспорта;

- управления производственными запасами

и многие другие, принадлежащие сфере оптимального планирования.

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

ЗЛП можно записать в сокращенном виде:

( )

( )

Оптимальным решением (планом) ЗЛП называется решение системы ограничений (2), при котором целевая функция принимает оптимальное значение.

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

Если все ограничения системы (1) - уравнения (вида «=»), то такую задачу называют задачей линейного программирования в каноническом виде (в канонической форме).

Справедливо утверждение. Любая ЗЛП может быть приведена к каноническому виду.

Приведем ограничения (1) к каноническом виду:

 

Теорема. Любому решению неравенства соответствует определенное решение уравнения в котором и наоборот.

 

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

 

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

 

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		-
			-

 

Прибыль, получаемая от единиц продукции и -соответственно 2 и 3 руб. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

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

(3)

По смыслу задачи переменные:

(4)

Суммарная прибыль составит руб. от реализации продукции и руб. от реализации продукции , т.е.:

(5)

Таким образом, получили экономико-математическую модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (3) и условию (4), при котором функция (5) принимает максимальное значение.

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

 

Питательное Вещество (витамин)	Необходимый минимум питательных веществ	Число единиц питательных веществ в 1 кг корма
		I	II

 

Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб. Необходимо составить такой дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не меньше установленного предела.

Решение. Составим экономико-математическую модель задачи. Пусть и - количество кормов I и II, соответственно, входящих в дневной рацион. Этот рацион будет включать единиц питательного вещества ; единиц питательного вещества ; единиц питательного вещества . Так как содержание питательных веществ , в рационе должно быть не менее, соответственно 9, 8, 12 единицы, получим систему неравенств:

(6)

По смыслу задачи переменные:

(7)

Общая стоимость рациона z составит в руб.:

(2)

Таким образом, получили экономико-математическую модель задачи: составить дневной рацион , удовлетворяющий системе (6) и условию (7), при котором функция (2) принимает минимальное значение.

 

Алгоритм симплекс-метода

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

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

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

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

V. Находим переменную, выводимую из базиса. Для этого составляем оценочные отношения (они заносятся в столбец для оценочных отношений) по следующим правилам:

1) , если и имеют разные знаки;

2) , если и ;

3) ли ;

4) 0, если и ;

5) , если и имеют одинаковые знаки.

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

VI. Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана):

1) В левом столбце записываем новый базис: вместо основной переменной - переменную ,

2) В столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1 - на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 - во всех других позициях столбцов базисных переменных.

3) Новую строку получаем из старой делением на разрешающий элемент .

4) Все остальные элементы вычисляем по правилу прямоугольника:

(12)

Далее переходим к шагу III.

Пример. Решить задачу:

Приведем систему ограничений к каноническому виду. Получим расширенную систему:

Целевую функцию представим в виде

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

Заполняем первую симплекс-таблицу:

 

Базис	Свободный	Переменные	Оценочные
	член							отношения
								18/3
		-2	-3

 

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

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

Переходим к новой симплекс-таблице:

а) в новом базисе основные переменные ;

б) расставляем 0 и 1; например, на пересечении столбца и строки, соответствующих переменной ставим 1, а остальные элементы столбца равны 0 и т.д. Третья строка получается делением на разрешающий элемент . Остальные клетки таблицы заполняем по формулам (12). Например:

Получаем вторую симплекс-таблицу:

 

Базис	Свободный	Переменные	Оценочные
	член							отношения
						-3
						-1		11/2
		-2

 

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

Переходим к новой симплекс-таблице:

 

Базис	Свободный	Переменные	Оценочные
	член							отношения
						-3
				-2				5/5
								5/1
				-3				12/9
						-3

 

и на этот раз критерий оптимальности не выполнен.

Выводимая переменная ; вводимая переменная- . Переходим к новой таблице.

 

Базис	Свободный	Переменные	Оценочные
	член							отношения
				-1/5	3/5
				-2/5	1/5
				2/5	-1/5
				3/5	-9/5
				4/5	3/5

 

Критерий оптимальности выполнен. Следовательно, Оптимальное решение

 

Пример.

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

Преобразуем систему ограничений, умножив первое и второе уравнение на .

Т -функция имеет вид: Заполняем первую симплекс-таблицу:

 

Базис	Свободный	Переменные	Оценочные
	член							отношения
		-1		-1
		-1
		-1	-2
	-М	М	-М	М			-M

 

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

 

Базис	Свободный	Переменные	Оценочные
	член							отношения
		-1		-1
		-3		-2			-2

 

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

 

Базис	Свободный	Переменные	Оценочные
	член		отношения
		-1		-1
		-3		-2

 

Пример.

Приведем ограничения к виду « »

Составим расширенную матрицу

Транспонируем матрицу

и сформулируем двойственную задачу:

 

Метод отсечения.

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

- оно должно быть линейным;

- оно должно отсекать найденный оптимальный нецелочисленный план;

- оно не должно отсекать ни одного целочисленного плана.

Такие ограничения называются правильными отсечениями.

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

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

Пример.

 

 

Построим область допустимых решений задачи. Это многоугольник АВСДЕ. Построим вектор градиент целевой функции . Ясно, что точкой оптимума будет точка В(3.5; 6.5). Полученное решение не удовлетворяет условию целочисленности. Проведем прямую , отсекающую точку В и не отсекающую ни одну целую точку. Получаем новый многоугольник , где и имеют целые координаты. Точка новое решение задачи целочисленного программирования.

Метод Гомори.

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

Оптимальное решение задачи

Пусть в этом оптимальном решении - не целая компонента.

 

Алгоритм метода Гомори

1. Решаем задачу симплекс методом. Если найденное решение целочисленно, то задача решена. Если задача не разрешима, то она не имеет решений и в целых числах.

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

3. Вводим дополнительную неотрицательную целую переменную и получаем новое уравнение

4. Полученную расширенную задачу решаем симплекс-методом. Если новый найденный план целочисленный, то задача решена, если нет то повторяем процедуру.

Замечание . - дробная часть числа .

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

Пример. Решить задачу в целых числах.

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

Построим симплекс-таблицу

 

Базис	Свободный	Переменные	Оценочные
	член						отношения
							17/2
	О	-2	-3

 

Данный план не оптимален, так как в оценочной строке есть отрицательные элементы. Наибольший по модулю находится в столбце . Следовательно переменная вводимая в базис. Построим оценочные отношения. Наименьшее соответствует строке . Значит вводимая в базис переменная. Переходим к новой симплекс-таблице.

Базис	Свободный	Переменные	Оценочные
	член						отношения
						-5	20/3
						-4	2/3
		-2

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

Базис	Свободный	Переменные	Оценочные
	член		отношения
					-1	-1
	2/3				1/3	-4/3
	76/3				2/3	1/3

 

Полученное решение оптимально, но не является цело

численным .

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

Найдем дробные части от чисел стоящих в фигурных скобках:

Получим неравенство

Введем дополнительную целую переменную

1234Следующая ⇒

Поделиться:

Популярное:

1. Ввод пробы с программированием температуры испарителя
2. Детерминированные модели принятия решений и динамическое программирование
3. Логику управления можно представить в виде схемы, важнейшими элементами которой являются: предвидение, решение, программирование, исполнение, контроль и анализ.
4. Модульное программирование на Ассемблере
5. Научно-техническое и инновационное программирование
6. Программирование алгоритма линейной структуры на языке Си
7. Программирование в принятии государственных решений
8. ПРОГРАММИРОВАНИЕ И МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
9. Программирование линейных вычислительных процессов
10. Программирование на языке Visual Basic
11. Программирование разветвляющихся и циклических процессов