Экономико-математическая модель.
Переменные:
х1 – количество изделий вида А, шт.
х2 – количество изделий вида В, шт.
х3 – количество изделий вида С, шт.
Целевая функция:
Минимум себестоимости изготовления изделий, тыс. рублей
L(х) = 10х1 + 17х2 + 18х3 → min
Максимум получения прибыли, тыс. рублей
C(х) = 4х1 + 2х2 + 4х3 → max
Максимум получаемой выручки, тыс. рублей
M(х) = 14х1 + 19х2 + 22х3 → max
Ограничения:
По ресурсу R1 2х1 + х2 + 3х3 ≤ 27
По ресурсу R2 2х1 + х2 + 4х3 ≤ 35
По ресурсу R3 3х1 + 2х2 + 6х3 = 44
Не отрицательность переменных х1, х2, х3 ≥ 0
Целочисленности х1, х2, х3 – целые
Канонический вид.
L(х) = – 10х1 – 17х2 – 18х3 → max
C(х) = 4х1 + 2х2 + 4х3 → max
M(х) = 14х1 + 19х2 + 22х3 → max
2х1 + х2 + 3х3 + х4 = 27
2х1 + х2 + 4х3 х5 = 35
3х1 + 2х2 + 6х3 = 44
х1, х2, х3 х4 х5 ≥ 0
х1, х2, х3 – целые
Решение однокритериальной задачи симплекс – методом. Послеоптимизационный анализ. Целочисленное решение.
Задание: решить однокритериальную задачу ЛП с целевой функцией «выручка» симплекс-методом. Выполнить послеоптимизационный анализ. Целочисленное решение получить методом Гомори и методом ветвей и границ.
С(х) = 14Х1 + 19Х2 + 22Х3 max – выручка
Ограничения по запасам:
Х1+Х2+3Х3 <= 27
2X1+3X2+4X3 <= 35
3X1+2X2+4X3 = 44
Х1,Х2,Х3 >= 0
Решаем задачу при условии максимизации выручки симплекс методом
Приводим к каноническому виду:
С(х) = 14Х1 + 19Х2 + 22Х3 max
Ограничения по запасам:
Х1+Х2+3Х3 + Х4 = 27
2X1+3X2+4X3 + Х5 = 35
3X1+2X2+4X3 = 44
Х1, Х2, Х3, Х4, Х5 >= 0
Вводим искусственный базис.
Х1+Х2+3Х3 + Х4 = 27
2X1+3X2+4X3 + Х5 = 35
3X1+2X2+4X3 + Х6 = 44
Х1, Х2, Х3, Х4, Х5, Х6 >= 0
Вводим новую целевую функцию(с искусственным базисом).
С(х) = -Х6 max
|
|
| 0 | 0 | 0 | 0 | 0 | -1 |
|
|
|
| 14 | 19 | 22 | 0 | 0 | 0 |
|
С | Базис | В | А1 | А2 | А3 | А4 | А5 | А6 |
|
0 | A4 | 27 | 2 | 1 | 3 | 1 | 0 | 0 | 9 |
0 | A5 | 35 | 2 | 1 | 4 | 0 | 1 | 0 | 8,75 |
-1 | A6 | 44 | 3 | 2 | 6 | 0 | 0 | 1 | 7,333333 |
| C(x)/j | -44 | -3 | -2 | -6 | 0 | 0 | 0 |
|
|
|
| 0 | 0 | 0 | 0 | 0 | -1 |
|
|
| 14 | 19 | 22 | 0 | 0 | 0 |
С | Базис | В | А1 | А2 | А3 | А4 | А5 | А6 |
0 | A4 | 5 | 0,5 | 0 | 0 | 1 | 0 | -0,5 |
0 | A5 | 5,666667 | 0 | -0,33333 | 0 | 0 | 1 | -0,66667 |
0 | A3 | 7,333333 | 0,5 | 0,333333 | 1 | 0 | 0 | 0,166667 |
| C(x)/j | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
|
|
| 14 | 19 | 22 | 0 | 0 |
С | Базис | В | А1 | А2 | А3 | А4 | А5 |
0 | A4 | 5 | 0,5 | 0 | 0 | 1 | 0 |
0 | A5 | 5,666667 | 0 | -0,33333 | 0 | 0 | 1 |
22 | A3 | 7,333333 | 0,5 | 0,333333 | 1 | 0 | 0 |
| C(x)/j | 161,3333 | -14 | -19 | 0 | 0 | 0 |
|
|
| 14 | 19 | 22 | 0 | 0 |
С | Базис | В | А1 | А2 | А3 | А4 | А5 |
0 | A4 | 5 | 0,5 | 0 | 0 | 1 | 0 |
0 | A5 | 13 | 0,5 | 0 | 1 | 0 | 1 |
19 | A2 | 22 | 1,5 | 1 | 3 | 0 | 0 |
| C(x)/j | 418 | 14,5 | 0 | 57 | 0 | 0 |
Ответ: С(х) = 418; Х*=(0; 22; 0)
У задачи сразу нашлось целочисленное решение, поэтому применение метода Гомори и метода Ветвей и границ(которые нужны для получения целочисленного решения), к сожалению, не требуется.
Отчет по устойчивости
Изменяемые ячейки |
|
|
|
| |||||||
|
|
| Результ. | Нормир. | Целевой | Допустимое | Допустимое | ||||
| Ячейка | Имя | значение | стоимость | Коэффициент | Увеличение | Уменьшение | ||||
| $N$2 | х1 | 0 | -14,5 | 14 | 14,5 | 1E+30 | ||||
| $N$3 | х2 | 22 | 0 | 19 | 1E+30 | 9,666666667 | ||||
| $N$4 | х3 | 0 | -35 | 22 | 35 | 1E+30 | ||||
|
|
|
|
|
|
|
| ||||
Ограничения |
|
|
|
|
| ||||||
|
|
| Результ. | Теневая | Ограничение | Допустимое | Допустимое | ||||
| Ячейка | Имя | значение | Цена | Правая часть | Увеличение | Уменьшение | ||||
| $M$5 | R1 | 22 | 0 | 27 | 1E+30 | 5 | ||||
| $M$6 | R2 | 22 | 0 | 35 | 1E+30 | 13 | ||||
| $M$7 | R3 | 44 | 9,5 | 44 | 10 | 44 |
Для того, чтобы получить максимальную выручку от реализации произведенной продукции, равную 418 тыс. руб., нужно изготавливать 0 шт. изделия А, 22 шт. изделия В и 0 шт. изделия С.
Допустимое увеличение, допустимое уменьшение таблицы «изменяемые ячейки» – показывает границы изменений коэффициентов целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение. Например, если стоимость изделия А увеличится(из-за каких-либо изменений на рынке) на 14,5 и более единиц, то изменится набор переменных, входящих в оптимальное решение. Уменьшаться цена этого изделия может до нуля, без изменения структуры плана. Цена изделия В может уменьшаться на 9,6667 ед. и неограниченно увеличиваться без изменения структуры плана. Цена на продукт С может изменяться в диапазоне от 0 до 35 без изменения структуры плана.
Результирующее значение таблицы ограничений - значение левой части ограничения при оптимальном плане. Т.е. сколько фактически использовано ресурса. Например, ресурса R1 – 22 ед., ресурса R2 – 22, а ресурса R3 – 44.
Теневая цена – изменение целевой функции при изменении ресурса на 1 единицу. Теневая цена недефицитного ресурса будет равна 0. Например, изменения количества ресурса R1 или ресурса R2 не повлияет на значение целевой функции (= 0), а увеличение запаса ресурса R3 приведет к увеличению выручки на 9,5 единиц. Допустимое увеличение, допустимое уменьшение таблицы ограничений - показывает, насколько можно изменить правую часть ограничения до того момента пока это будет влиять на структуру целевой функции. Например, увеличение ресурсов R1 и R2 никак не повлияет на целевую функцию. Уменьшение же ресурса R1 более чем на 5 единиц или ресурса R2 более чем на 13 единиц приведет к изменению структуры плана. Ресурс R3 может изменяться в диапазоне от 10 до 44 единиц без изменения структуры плана.
- Оглавление
- Введение
- Постановка задачи
- Теоретические основы решения задач
- Экономико-математическая модель.
- Решение однокритериальных задач с параметром в целевой функции и в ограничениях.
- Параметр в целевой функции
- Параметр в правой части ограничений
- Решение многокритериальной задачи
- Выводы по работе
- Список использованной литературы