Xreferat.com » Рефераты по математике » Задачи математического программирования

Задачи математического программирования

Рисунок 1 – Графический метод

 


Из рисунка 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 =

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: