Лабораторная работа №1 (Задача линейного программирования)

Задание:

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

Решить задачу графическим методом;

Привести задачу к канонической форме записи;

Составить симплексную таблицу;

Произвести решение задачи симплексным методом ручным способом или с использование компьютера;

Осуществить постановку двойственной задачи ЛП;

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

Проверить результаты решения в табличном процессоре Excel;

Составить отчет с приведение результатов по каждому пункту.

Решение:

Графический метод. Для построения многоугольника решений преобразуем исходную систему

, получим

изобразим граничные прямые.

Линейная функция 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.

Она уже соответствует опорному плану 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, а разрешающей строкой - х4. Далее действуем по тому же алгоритму.

Таблица 3.

Следующим разрешающим столбцом будет столбец х5, а разрешающей строкой - х3. Далее действуем по тому же алгоритму.

Таблица 4.

Конечная симплексная таблица:

Все коэффициенты в строке целевой функции положительны, т.е. мы нашли оптимальное решение.

Таким образом, в точке 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.

Проверить результаты решения в табличном процессоре Excel. В Excel имеется надстройка «Поиск решения», которая позволяет решать оптимизационные задачи.

Использовав эту надстройку для решения нашей задачи ЛП, получаем следующий результат:

Таблица 6.

Но при применении надстройки «поиск решения» к задаче, двойственной данной задаче ЛП, приходим к выводу, что решение полученное с помощью надстройки не сходится с решением из симплекс-таблицы:

Таблица 7.