Курсовая работа: Задачи математического программирования
Составить отчет с приведение результатов по каждому пункту.
| Ресурсы | Запасы | Продукция | |
| Р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.
|
Из рисунка 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 остальные элементы разрешающей строки делятся на разрешающий элемент;