Лекция 1 Задачи линейного программирования

Лекция 1 Задачи линейного программирования

1. Задача оптимального планирования производства

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

Обозначим через  величину прибыли от реализации одной единицы j -го вида продукции. Эти значения прибыли запишем матрицей-строкой . План производства продукции х ₁, х ₂, …, х_п обозначим матрицей-столбцом Х. Тогда произведение матриц  представляет собой величину прибыли, полученной после реализации продукции.

Количество i -го ресурса обозначим . Значения    b ₁, b ₂, …, b_m  запишем матрицей-столбцом B. Тогда матричное неравенство  означает необходимость, учитывать ограниченность ресурсов при рассмотрении планов производства Х. Если это неравенство выполняется, то план  является реальным или допустимым. Естественно, нужно найти такой допустимый план, который бы обеспечил наибольшую прибыль.

Эту задачу можно записать так:

 

 

 

.

 

Или в матричной форме:

,

, .

 

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

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

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

 

 

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

Программирования

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

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

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

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

Пример. Решить графическим методом задачу линейного программирования: найти максимальное значение функции  при ограничениях

 

 

,

;

, .

 

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

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

 

 

Находим координаты точки В, для этого решаем систему уравнений:

 

 

Найденные координаты точки  подставляем в целевую функцию, и определяем максимальное значение:

 

.

 

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

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

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

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

Для реализации симплекс-метода необходимо определить: 1) первоначальное допустимое решение задачи, 2) правило перехода к лучшему решению, 3) критерий проверки оптимальности найденных решений. Для этого составляются различные алгоритмы симплекс-метода. Рассмотрим один из них для нахождения максимального значения целевой функции на следующем примере.

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

 

 

1. Вводим новые переменные , с помощью которых неравенства системы преобразуем в уравнения:

 

 

У коэффициентов целевой функции меняем знак или записываем ее в виде . Заполняем первую симплексную таблицу, в нулевой строке записываем х ₁, х ₂ и  (свободные коэффициенты). В нулевом столбце – х ₃, х ₄, х ₅ и F. Заполняем эту таблицу по полученной системе уравнений и преобразованной целевой функции.

 

 

	5	3	15
	-2	3	6
	3	-1	3
	-2	-3	0

     

 

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

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

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

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

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

 

.

 

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

 

	х1	х4	b				х3	х2	b
х3	7	-1	9			х1
х2			2			х2
х5			5			х5			2
F	-4	1	6			F

 

 

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

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

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

 

Пример решения матричной игры средствами Excel

       Решим, используя надстройку «Поиск решения» Excel  игру, заданную матрицей

 

.

  Нижняя и верхняя цены игры:

 

= max(l;3) = 3;

не совпадают, поэтому применяем смешанные стратегии.

       Для нахождения оптимальной стратегии первого игрока решаем задачу линейного программирования: найти минимальное значение функции  при ограничениях

 

 

,

;

, .

 

        Здесь ,   где  вероятность выбора первой строки  вероятность выбора второй строки,  цена игры.

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

 

	A	B	C	D
1	u1	u2	L
2
3	1	1
4	1	6		1
5	9	3		1

 

Вводим зависимости для целевой функции и системы ограничений. Для этого в ячейку С2 вводим формулу =СУММПРОИЗВ(A2:B2;A3:B3). В ячейки С4 и С5 соответственно формулы: =СУММПРОИЗВ(A2:B2;A4:B4) и =СУММПРОИЗВ(A2:B2;A5:B5). В результате получаем таблицу.

	A	B	C	D
1	u1	u2	L
2			0
3	1	1
4	1	6	0	1
5	9	3	0	1

 

 

Запускаем команду «Поиск решения» и заполняем появившееся окно Поиск решения следующим образом. В поле «Оптимизировать целевую функцию» вводим ячейку С2. Выбираем оптимизации значения целевой ячейки «Минимум».

 В поле «Изменяя ячейки переменных» вводим изменяемые ячейки A2:B2. В поле «В соответствии с ограничениями» вводим заданные ограничения с помощью кнопки «Добавить». Ссылки на ячейку $C$4:$C$5 Ссылки на ограничения =$D$4:$D$5 между ними знак => затем кнопку «ОК».

Ставим флажок в поле «Сделать переменные без ограничений неотрицательными». Выбрать метод решения «Поиск решения линейных задач симплекс-методом». 

Нажатием кнопки «Найти решение» запускается процесс решения задачи. В итоге появляется диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками для значений переменных и оптимальным значением целевой функции.

 

 

	A	B	C	D
1	u1	u2	L
2	0,058824	0,156863	0,215686
3	1	1
4	1	6	1	1
5	9	3	1	1

 

В диалоговом окне «Результаты поиска решения» сохраняем результат u1=0,058824, u2=0,156863, L=0,215686-равный минимальному значению целевой функции. Заметим, что нужное количество знаков после запятой можно ввести, выбрав команду Формат ячеек.

Так как  и , , то находим, что =4,63637, =0,272728 0,27, =0,727274 0,73 с такими вероятностями первый игрок должен выбирать первую и вторую строки.

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

 

Здесь ,   где  вероятность выбора первогостолбца  вероятность выбора второго столбца,  цена игры.

Решение этой задачи с использованием надстройки «Поиск решения» Excel  дано в таблице

 

	A	B	C	D
1	t1	t2	L
2	0,117647	0,098039	0,215686
3	1	1
4	1	9	1	1
5	6	3	1	1

Так как  и , , то находим, что =4,63637, =0,545455 0,55, =0,454546 0,45 с такими вероятностями второй игрок должен выбирать первый столбец и второй.

 

Пример решения транспортной задачи средствами Excel

 

Рассмотрим решение транспортной задачи заданной таблицей

 

Bj Ai	60	70	110
150	10	12	6
90	5	5	8

 

используя надстройку «Поиск решения» Excel.

 

  На рабочем листе Excel вводим исходные данные в виде таблицы

 

 

	A	B	C	D	E
1	10	12	6
2	5	5	8
3
4				0	150
5				0	90
6	0	0	0	0
7	60	70	110

 

 

Здесь в ячейках  введены стоимости перевозок. Ячейки  отведены под неизвестные значения объемов перевозок. В ячейках  введены объемы поставок, а в ячейках  объемы потребностей.

В ячейку , вводится формула для целевой функции =СУММПРОИЗВ(A1:C2;A4:C5).

В ячейки  вводятся формулы: =СУММ(A4:A5); =СУММ(B4:B5): =СУММ(C4:C5) определяющие объемы потребностей.

В ячейки  введены формулы: =СУММ(A4:C4); =СУММ(A5:C5) характеризующие объемы поставок

Запускаем команду «Поиск решения» и заполняем появившееся окно Поиск решения следующим образом. В поле «Оптимизировать целевую функцию» вводим ячейку . Выбираем оптимизации значения целевой ячейки «Минимум».

 В поле «Изменяя ячейки переменных» вводим изменяемые ячейки . В поле «В соответствии с ограничениями» вводим заданные ограничения с помощью кнопки «Добавить». $A$6:$C$6=$A$7:$C$7 $D$4:$D$5<=$E$4:$E$5.

Ставим флажок в поле «Сделать переменные без ограничений неотрицательными». Выбрать метод решения «Поиск решения линейных задач симплекс-методом». 

Нажатием кнопки «Найти решение» запускается процесс решения задачи. В итоге появляется диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками для значений переменных и оптимальным значением целевой функции.

 

	A	B	C	D	E
1	10	12	6
2	5	5	8
3
4	40	0	110	150	150
5	20	70	0	90	90
6	60	70	110	1510
7	60	70	110

 

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

Лекция 4. Сетевое планирование

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

 

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

 

 

Работа	Содержание	Продолжительность, дни
(1, 2)	Определение объема работы	5
(2, 3)	Составление сметы	10
(2, 6)	Выбор проекта реконструкции	5
(3, 4)	Выбор подрядчика	3
(3, 5)	Открытие счета в банке	2
(3, 8)	Утверждение сметы вышестоящей организацией	5
(4, 8)	Составление договора с подрядчиком	3
(5, 8)	Сообщение заказчику об открытии счета в банке	1
(6, 7)	Экономическое обоснование проекта	4
(7, 8)	Привязка проекта к площади предприятия	5
(8, 9)	Работы по реконструкции	60

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

 

1) Ранние возможные сроки:

 

(1) = 0

 (2) = 0+5 = 5

  (3) = 5+10 = 15

 (4) = 15+3 = 18

 (5) = 15+2 = 17

  (6) = 5+5 = 10

 (7) = 10+4 = 14

(8) = (14+5;18+3;15+5;17+1)= (19;21;20;18)=21

 (9) = 21+60 = 81

 

2) Поздние допустимые сроки:

 

  (9) =  (9) = 81

  (8) = 81-60 = 21

 (7) = 21-5 = 16

  (6) = 16-4 = 12

 (5) = 21-1 = 20

 (4) = 21-3 = 18

  (3) = (18-3; 21-5; 20-2) =  (15; 16;18) = 15

 (2) = (12-5; 15-10) =  (7;5) = 5

 (1) = 5-5 = 0

 

Критический путь содержит 5 работ: (1,2); (2,3); (3,4); (4,8); (8,9).

Минимальный срок: 5+10+3+3+60 = 81 день.

Таблица резервов времени

 

Работа	Длительность работы	Начало работы		Конец работы		Резервы времени
						ПР	ГР	СР	НР
(2,6)	5	5	5	10	12	2	2	0	0
(6,7)	4	10	12	14	16	2	0	0	0
(7,8)	5	14	16	21	21	2	0	2	0
(3,5)	2	15	15	17	20	3	3	0	0
(3,8)	5	15	15	21	21	1	1	1	1
(5,8)	1	17	20	21	21	3	0	3	0

Пример решения задача о распределении средств между предприятиями

 

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

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

 

 

Выделяемые средства, млн.руб.	Прирост выпуска продукции, млн. руб.
	Предприятие № 1	Предприятие № 2	Предприятие № 3	Предприятие № 4
20	3	2	2	1
40	5	4	4	3
60	7	5	5	6
80	9	7	8	7
100	10	9	10	9

 

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

Решение будем проводить согласно рекуррентным соотношениям.

Этап 1. Инвестиции производим только первому предприятию. Тогда

f ₁(20)=3, f ₂(40)=5, f ₃(60)=7, f ₄(80)=9, f ₅(100)=10.

Этап 2. Инвестиции выделяем первому и второму предприятиям. Рекуррентное соотношение (1) примет вид:

f ₂(x)=max{ g ₂(x ₂)+ f ₁(x - x ₂)}.

Следовательно

f ₂(20)=max(3+0, 0+2)=max(3, 2)=3.

f ₂(40)=max(5+0, 3+2, 0+4)=max(5, 5, 4)=5.

f ₂(60)=max(7+0, 5+2, 3+4, 0+5)=max(7, 7, 7, 5)=7.

f ₂(80)=max(9+0, 7+2, 5+4, 3+5, 0+7)=max(9, 9, 9, 8, 7)=9.

f ₂(100)=max(10+0, 9+2, 7+4, 5+5, 3+7, 0+9)=max(10, 11, 11, 10, 10, 9)=11.

Этап 3. Финансируем второй этап и третье предприятие. В этом случае соотношение (1) принимает вид:

f ₃(x)=max{ g ₃(x ₃)+ f ₂(x - x ₃)}.

Тогда

f ₃(20)=max(3+0, 0+2)=max(3, 2)=3.

f ₃(40)=max(5+0, 3+2, 0+4)=max(5, 5, 4)=5.

f ₃(60)=max(7+0, 5+2, 3+4, 0+5)=max(7, 7, 7, 5)=7.

f ₃(80)=max(9+0, 7+2, 5+4, 3+5, 0+8)=max(9, 9, 9, 8, 8)=9.

f ₃(100)=max(11+0, 9+2, 7+4, 5+5, 3+8, 0+10)=max(11, 11, 11, 10, 11, 10)=11.

Этап 4. Инвестиции в объеме 100 млн.руб. распределяем между третьим этапом и четвертым предприятием. Соотношение (1) принимает вид:

f ₄(x)=max{ g ₄(x ₄)+ f ₃(x - x ₄)}.

Следовательно

f ₄(20)=max(3+0, 0+1)=max(3, 1)=3.

f ₄(40)=max(5+0, 3+1, 0+3)=max(5, 4, 3)=5.

f ₄(60)=max(7+0, 5+1, 3+3, 0+6)=max(7, 6, 6, 6)=7.

f ₄(80)=max(9+0, 7+1, 5+3, 3+6, 0+7)=max(9, 8, 8, 9, 7)=9.

f ₄(100)=max(11+0, 9+1, 7+3, 5+6, 3+7, 0+9)=max(11, 10, 10, 11, 10, 9)=11.

Максимальный прирост выпуска продукции в 11 млн.руб. получен на четвертом этапе как, например, 5+6, т.е. 6 млн.руб. соответствуют выделению 60 млн.руб. четвертому предприятию. Согласно третьему этапу 5 млн.руб. получено как 3+2, т.е. 2 млн.руб. соответствует выделению 20 млн.руб. третьему предприятию. Согласно второму этапу 3 млн.руб. получено как 3+0, те. 3 млн.руб. соответствует выделению 20 млн.руб. первому предприятию.

Таким образом, инвестиции в объеме 100 млн. руб. целесообразно выделить четвертому предприятию в объеме 60 млн.руб. и первому и второму предприятиям в объеме по 20 млн.руб. каждому, при этом прирост продукции будет максимальным и составит 11 млн.руб.

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

 

x
0	0	0	0	0	0	0	0	0
20	3	3	2		2		1
40	5	5	4		4		3
60	7	7	5		5		6
80	9	9	7		7		7
100	10	10	9		9		9

 

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

 

x
0	0	0	0	0	0	0	0	0
20	3	3	2	3	2	3	1	3
40	5	5	4	5	4	5	3	5
60	7	7	5	7	5	7	6	7
80	9	9	7	9	7	9	7	9
100	10	10	9	11	9	11	9	11

 

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

В пакете «Stadia»

 

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

В ходе анализа можно получить следующие результаты:

– выбрать из нескольких математических моделей ту, которая с большей точностью описывает экспериментальную зависимость (нами будет рассмотрена только линейная модель);

– построить прогноз на будущее на основе выбранн