Лабораторная работа №1 (Задача линейного программирования)
Задание:
Для заданной математической постановки задачи ЛП, приняв дополнительно условие неотрицательности переменных, выполнить следующие действия:
Решить задачу графическим методом;
Привести задачу к канонической форме записи;
Составить симплексную таблицу;
Произвести решение задачи симплексным методом ручным способом или с использование компьютера;
Осуществить постановку двойственной задачи ЛП;
Получить решение двойственной задачи из полученной ранее симплексной таблицы и произвести анализ полученных результатов;
Проверить результаты решения в табличном процессоре Excel;
Составить отчет с приведение результатов по каждому пункту.
Ресурсы |
Запасы |
Продукция |
||
Р1 |
Р2 |
|||
S1 |
18 |
0.2 |
3 |
|
S2 |
13.1 |
0.7 |
2 |
|
МВ |
23 |
2.3 |
2 |
|
Прибыль от единицы продукции в У.Е. |
3 |
4 |
Решение:
Графический метод. Для построения многоугольника решений преобразуем исходную систему
, получим
изобразим граничные прямые.
Линейная функция F=f(x) является уравнением прямой линии c1x1 + c2x2 = const. Построим график целевой функции при f(x)=0. для построения прямой 3x1 + 4x2 = 0 строим радиус-вектор N = (3; 4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую F=0 перемещаем параллельно самой себе в направлении вектора N.
39
Из рисунка 1 следует, что опорной по отношению к построенному многоугольнику решений эта прямая становится в точке B, где функция F принимает максимальное значение. Точка В лежит на пересечении прямых 0,7x1 + 2x2 ? 13,1 и 2,3x1 + 2x2 =23/ Для определения ее координат решим систему уравнений:
Оптимальный план задачи: х1 = 6.187; х2 = 4.38, подставляя значения х1 и х2 в целевую функцию, получаем Fmax= 3*6.187+4*4.38=36.08.
Таким образом, для того, чтобы получить максимальную прибыль в размере 36.06 долларов, необходимо запланировать производство 6 ед. продукции P1 и 4 ед. продукции P2.
Канонический вид задачи ЛП. Запишем в канонической форме задачу распределения ресурсов. Добавив к исходной системе ограничений неотрицательные переменные х3 ? 0, х4 ? 0, х5 ? 0, имеем:
При этом в далее получаемом решении переменные х3 и х4 будут соответствовать объемам неиспользованного сырья S1 и S2, а х5 - неиспользованному машинному времени.
Симплексная таблица ЛП. В случае базисных переменных {x3, x4, x5} начальная симплекс таблица будет выглядеть:
Таблица 1.
-х1 |
-х2 |
|||
х3 = |
0,2 |
3 |
18 |
|
х4 = |
0,7 |
2 |
13,1 |
|
х5 = |
2,3 |
2 |
23 |
|
f(x) = |
3 |
4 |
Она уже соответствует опорному плану x(0) = [0 0 18 13,1 23]Т (столбец свободных членов).
Симплексный метод решения задачи ЛП. Для того, чтобы опорный план был оптимален, при максимизации целевой функции необходимо, чтобы коэффициенты в строке целевой функции были неотрицательными, т.е. при поиске максимума мы должны освободиться от отрицательных коэффициентов в строке f(x).
Алгоритм симплекс метода.
1. Выбор разрешающего столбца. В качестве разрешающего выбираем столбец с минимальным коэффициентом в строке f(x). В данном примере это столбец х2.
2. Выбор разрешающей строки. Для выбора разрешающей строки (разрешающего элемента) среди положительных коэффициентов разрешающего столбца выбираем тот элемент, для которого отношение коэффициентов в столбце свободных членов к коэффициенту в разрешающем столбце минимально. Разрешающий элемент рассчитывается по формуле:
В данном примере такой строкой будет строка х3, т.к. отношение коэффициента в столбце свободных членов к коэффициенту в разрешающем столбце минимально.
3. Замена базиса. Для перехода к следующей симплексной таблице (следующему опорному плану с большим значением целевой функции) делаем шаг модифицированного жорданова исключения с разрешающим элементом arl, при котором базисная переменная xr становится свободной и одновременно свободная переменная xi становится базисной.
3.1 на месте разрешающего элемента ставится 1 и делится на разрешающий элемент;
3.2 остальные элементы разрешающего столбца меняют знак на противоположный и делятся на разрешающий элемент;
3.3 остальные элементы разрешающей строки делятся на разрешающий элемент;
3.4. все остальные элементы симплексной таблицы вычисляются по формуле:
3.5. элементы правого столбца и нижней строки пересчитываются по тому же принципу, что и элементы в центральной части таблицы.
Симплексная таблица, рассчитанная по алгоритму:
Таблица 2.
-х1 |
-х3 |
|||
х2 = |
0,067 |
0,3 |
6 |
|
х4 = |
0,57 |
-0,67 |
1,1 |
|
х5 = |
2,17 |
-0,67 |
11 |
|
f(x) = |
-3,27 |
1,3 |
72,6 |
Следующим разрешающим столбцом будет столбец х1, а разрешающей строкой - х4. Далее действуем по тому же алгоритму.
Таблица 3.
-х4 |
-х3 |
1 |
||
х2 = |
-0,1 |
0,24 |
5,87 |
|
х1 = |
1,75 |
-1,17 |
1,03 |
|
х5 = |
-3,8 |
1,88 |
5,8 |
|
f(x) = |
5,7 |
-2,5 |
35,06 |
Следующим разрешающим столбцом будет столбец х5, а разрешающей строкой - х3. Далее действуем по тому же алгоритму.
Таблица 4.
-х4 |
-х5 |
1 |
||
х2 = |
0,39 |
-0,13 |
4,4 |
|
х1 = |
-0,61 |
0,6 |
6,19 |
|
Х3 = |
-2 |
0,53 |
1,3 |
|
f(x) = |
0,64 |
1,3 |
36,08 |
Конечная симплексная таблица:
Все коэффициенты в строке целевой функции положительны, т.е. мы нашли оптимальное решение.
Таким образом, в точке x1 = 4, x2 = 6, x3 = 1,3, x4 = 0, x5 = 0 целевая функция принимает максимальное значение f(x) = 36.
При этом переменным, которые стоят в верхней строке, в базисном решении присваивается значение 0 - это свободные переменные. Каждая из переменных, стоящая в левом столбце, приравнивается к числу, записанному в правом столбце той же самой строки - это базисные переменные.
Постановка двойственной задачи ЛП. Определить значение двойственных оценок можно следующим образом. если некоторый i-тый ресурс используется не полностью, т.е. имеется резерв, значит дополнительная переменная в ограничении для данного ресурса будет больше нуля. Очевидно, что при увеличении общего машинного времени не произошло бы увеличение целевой функции. Следовательно, машинное время не влияет на прибыль и для третьего ограничения двойственная переменная y3 = 0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка данного ограничения равна нулю.
В данном примере оба вида сырья использовались полностью, поэтому их дополнительные переменные равны нулю (в итоговой симплексной таблице переменные х3 и х4 являются свободными, значит х3 = х4 = 0). Если ресурс использовался полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции и, следовательно, на величину целевой функции. Значение двойственной оценки при этом находится в симплекс-таблице на пересечении строки целевой функции со столбцом данной дополнительной переменной.
Получить решение двойственной задачи из полученной ранее симплексной таблицы и произвести анализ полученных результатов. Формулировка и результаты решения исходной и двойственной задач распределения ресурсов приведены в таблице 4.
Таблица 4.
Исходная задача ЛП |
Двойственная задача ЛП |
|
Математическая постановка |
||
Обозначения и интерпретация параметров задачи |
||
xj, j = - количество производимой продукции j-го вида; f(x) - общая прибыль от реализации продукции |
yi, i = - стоимость единицы i-го ресурса; - стоимость всех имеющихся ресурсов |
|
Экономическая интерпретаци язадачи |
||
Сколько и какой продукции необходимо произвести, чтобы пр заданных стоимостях cj, j = еддиницы продукции и размерах имеющихся ресурсов bi, i = максимизировать общую прибыль? |
Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных их количествах bi, i = и величинах стоимости единицы продукции cj, j = минимизировать общую стоимость затрат? |
|
Результаты решения |
||
Результирующая симплекс-таблица -х4 -х5 1 х2 = … … 4,4 х1 = … … 6,19 Х3 = … … 1,3 f(x) = 0,64 1,3 36,08 Основные переменные х1 = 6,19 х2 = 4,4 дополнительные переменные х3 = 1,3 х4 = 0 х5 = 0 |
Дополнительные переменные y4 = 0 y5 = 0 основные переменные y1 = 0,64 y2 = 1,3 y3 = 0 |
|
Интерпретация дополнительных переменных |
||
xn+1, …., xn+m - неиспользованное (резервное) количество соответствующего ресурса (при наличие резервного ресурса соответствующая двойственная переменная навна 0) |
ym+1, …, ym+n - насколько уменьшится целевая функция при принудительном выпуске единицы данной продукции (если какая-либо из основных переменных исходной задачи равна 0) |
Проверить результаты решения в табличном процессоре Excel. В Excel имеется надстройка «Поиск решения», которая позволяет решать оптимизационные задачи.
Использовав эту надстройку для решения нашей задачи ЛП, получаем следующий результат:
Таблица 6.
Переменные |
Целевая функция |
|||||
Вид продукции |
Р1 |
Р2 |
Прибыль |
|||
Значение |
6,1875 |
4,3844 |
36,1 |
|||
Прибыль от ед. прод. |
3 |
4 |
макс |
|||
Ограничения |
||||||
Типы ресурсов |
Р1 |
Р2 |
Расход ресурсов |
Знак |
Запас ресурсов |
|
Сырье S1 |
0,2 |
3 |
14,390625 |
<= |
18 |
|
СырьеS2 |
0,7 |
2 |
13,1 |
<= |
13,1 |
|
Машинное время |
2,3 |
2 |
23 |
<= |
23 |
Но при применении надстройки «поиск решения» к задаче, двойственной данной задаче ЛП, приходим к выводу, что решение полученное с помощью надстройки не сходится с решением из симплекс-таблицы:
Таблица 7.
Переменные |
||||||||
имя |
x1 |
x2 |
f(x) |
|||||
значение |
6,19 |
4,38 |
36,1 |
|||||
коэф-ты f(x) |
3 |
4 |
макс |
|||||
Ограничения |
двойств. Оценки |
|||||||
№ |
x1 |
x2 |
левая часть |
знак |
правая часть |
y |
||
1 |
8 |
3 |
62,653125 |
<= |
18 |
1,333333 |
||
2 |
0,7 |
2 |
13,1 |
<= |
13,1 |
0 |
||
3 |
2,3 |
2 |
23 |
<= |
23 |
0 |
||
Ограничения двойственной задачи |
Целевая функция двойственной задачи |
|||||||
10,66667 |
4 |
24 |
- Введение
- 1. Понятие математического программирования
- 2. Понятие линейного программирования. Виды задач линейного программирования
- 3. Понятие нелинейного программирования
- 4. Динамическое программирование
- Лабораторная работа №1 (Задача линейного программирования)
- Лабораторная работа № 2 (Решение задачи ЛП средствами табличного процессора Excel)
- Лабораторная работа № 3 (Решение транспортной задачи)
- Лабораторная работа №4 (решение задач нелинейного программирования)
- Лабораторная работа №5 (задача динамического программирования об оптимальном распределении инвестиций)
- Лабораторная работа №5 (задача динамического программирования о выборе оптимального пути в транспортной сети)
- Заключение
- Классификация задач математического программирования
- 1.1. Задачи математического и линейного программирования
- Общая задача математического программирование
- 1. Определение задачи математического программирования
- Классификация задач математического программирования
- 5.1 Классификация задач математического программирования
- 1.3. Классификация задач математического программирования
- Формулировка задачи математического программирования
- 21.Задачи математического программирования.