Реферат Комплекс и симпплекс методы решения задач по оптимизации бизнеса
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Задание
Дано:
затраты сырья на единицу продукции заданы матрицей затрат;
| МАТРИЦА ЗАТРАТ | |||
| Вид | В1 | В2 | Запас |
| А1 | 5 | 6 | 42 |
| А2 | 7 | 3 | 36 |
| А3 | 2 | 4 | 74 |
| цена | 5 | 4 | |
стоимость реализации равна: р1 = 5, р2 = 4;
Требуется:
1) Составить исходную задачу, обеспечивающую максимальную прибыль.
2) Составить двойственную задачу к исходной.
3) Первую задачу решить графическим методом, вторую задачу решить симплекс-методом.
Решение
1).
Для частной экономической модели введем обозначение:
Xj; где: Хj – количество продукции j – того вида, Xj ≥0.
Составим ограничение по ресурсам в виде системы неравенств:
5хХ1+5хХ2≤42
7хХ1+3хХ2≤36
2хХ1+4хХ2≤74
Среди неотрицательных решений системы неравенств необходимо найти такое, которое соответствует случаю получения максимальной прибыли:
L=5хХ1+4хХ2 => max
Это и есть математическая форма исходной задачи, решение которой обеспечивает максимальную прибыль.
2).
Теперь составим задачу, двойственную к исходной.
Это будет задача по обеспечению минимализации затрат.
Для частной экономической модели введем обозначение:
Yj; где: Yj – стоимость ресурсов j – того вида, Yj ≥0.
Составим ограничение по стоимости ресурсов в виде системы неравенств:
5хY1+7хY2+2xY3≥5
6хY1+3хY2+4xY3≥4
Среди неотрицательных решений системы неравенств необходимо найти такое, которое соответствует случаю обеспечения минимальных затрат:
Z=42хY1+36хY2+74xY3 => min
Это и есть математическая форма задачи, двойственной к исходной, решение которой обеспечивает минимальные затраты.
3).
Решим первую задачу графическим методом
Для исходной системы неравенств определяем линии границ и точки их пересечений с осями координат:
5хХ1+6хХ2≤42 5хХ1+6хХ2=42 (0;7), (8,4;0).
7хХ1+3хХ2≤36 7хХ1+3хХ2=36 (0;12), (5 1/7;0).
2хХ1+4хХ2≤74 2хХ1+4хХ2=74 (0;18,5), (37;0).
Для множества решений системы неравенств лежащего в границах многоугольника ОАВС найдем координату точки В решив систему уравнений:
7хХ1+3хХ2=36 14хХ1+6хХ2=72 9хХ1=30 Х1=3 1/3
Х1=3,3 Х1=3,3 Х1=3,3 Х1=3,3
Среди неотрицательного множества решений системы неравенств, лежащего в границах четырехугольника ОАВС вычислим значения функции L в точках ОАВС:
L(0)=5х0+4х0=0+0=0; L(А)=5х0+4х7=0+28=28;
L(В)=5х3,3+4х4,25=16,5+17=33,5;
L(С)=5х5 1/7+4х0=25 5/7+0=25 5/7;
Функция L=5хХ1+4хХ2 принимает свое максимальное значение в точке В (3,3;4,25).
Ответ(1):
Максимальная прибыль будет обеспечена при одновременном производстве 3,3 штук товара № 1 и 4,25 штук товара № 2.
Решим вторую задачу симплекс-методом
Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:
6хY1+3хY2+4xY3≥4 6хY1+3хY2+4xY3+Y5=4
где: Yj – стоимость ресурсов j – того вида, Yj ≥0.
Среди неотрицательных решений системы неравенств необходимо найти такое, которое соответствует случаю обеспечения минимальных затрат:
Z=42хY1+36хY2+74xY3 +Y4+Y5 => min
Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод.
Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод, т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных.
| симплекс-метод итерация 0 | |||||||
| БП | Y1 | Y2 | Y3 | Y4 | Y5 | коэфф | контр |
| Y4 | 5 | 7 | 2 | 1 | 0 | 5 | 20 |
| Y5 | 6 | 3 | 4 | 0 | 1 | 4 | 18 |
| Z | -42 | -36 | -74 | 0 | 0 | 0 | -152 |
Здесь "БП" означает столбец базисных переменных
Решение не является оптимальным, т.к. в Z – строке есть отрицательные коэффициенты.
Для улучшения решения перейдем к следующей итерации симплекс-метода, получим следующую симплекс-таблицу.
Для этого надо выбрать разрешающий столбец, т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в Z-строке. Это столбец Y3.
Затем выбирается разрешающая строка, т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца «коэфф» к соответствующим положительным элементам разрешающего столбца, в начальной итерации (итерация 0) это строка Y5.
Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 4.
Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец Y3 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).
| симплекс-метод итерация 1 | |||||||
| БП | Y1 | Y2 | Y3 | Y4 | Y5 | коэфф | контр |
| Y4 | 2 | 5,5 | 0 | 1 | -0,5 | 3 | 11 |
| Y3 | 1,5 | 3/4 | 1 | 0 | 1/4 | 1 | 4?5 |
| Z | 69 | 19,5 | 0 | 0 | 18,5 | 74 | 181 |
В Z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение.
Z=42хY1+36хY2+74xY3 +Y4+Y5 =42х0+36х0+74=1+0х3+0х0=74.
Ответ(2):
Минимальные затраты Zmin= 74.
