Математические программирование
ЛАБОРАТОРНАЯ РАБОТА №2
по мат.программированию
«Графический и симплексный методы решения ОЗЛП»
Для изготовления 2-х различных изделий А и В используется 3 вида сырья. На производство единицы изделия А требуется затратить сырья 1-го вида а1 кг, сырья 2-го вида - а2 кг, сырья 3-го вида - а3 кг. На производство единицы изделия В требуется затратить сырья 1-го вида в1 кг, сырья 2-го вида - в2 кг, сырья 3-го вида - в3 кг. Производство обеспечено сырьём 1-го вида в количестве Р1 кг, сырьём 2-го вида в количестве Р2 кг, сырьём 3-го вида в количестве Р3 кг. Прибыль от реализации единицы готового изделия А составляет ден.ед., а изделия В - ден.ед.
|
№ | а1 | а2 | а3 | в1 | в2 | в3 | Р1 | Р2 | Р3 | | | |
8 | 11 | 7 | 8 | 10 | 5 | 6 | 425 | 450 | 550 | 2 | 4 | |
|
Математическая модель задачи
Обозначим количество произведенной продукции 1-го вида через х1, 2-го вида - х2. Тогда линейная функция примет вид: Z (х1, х2) =2*х1+4*х2.
Это есть цена произведенной продукции. Наше решение должно обеспечить максимальное значение этой функции.
Условие налагает на величины х1 и х2 ограничения следующего вида:
Построенная линейная функция называется функцией цели и совместно системой ограничений образует математическую модель рассматриваемой экономической задачи.
Графическое решение задачи
Построим многоугольник решений. Для этого в системе координат х1Ох2 на плоскости изобразим граничные прямые
Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Многоугольником решений данной задачи является треугольник АОВ. Для построения прямой 2*х1+4*х2=0 строим радиус-вектор N=(2;4)=2.5*(2;4)=(5;10) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z =0 перемещаем параллельно самой себе в направлении вектора N. Опорной по отношению к многоугольнику решений эта прямая становится в точке А (0;42,5), где функция Z принимает максимальное значение.
Оптимальный план задачи: х1=0; х2=42,5.
Подставляя значения х1 и х2 в линейную функцию, получаем Zmax=2*0+4*42.5=170 у.е.
Таким образом, для того чтобы получить максимальную прибыль в размере 170 у.е., необходимо запланировать производство 42,5 ед. продукции В.
Решение задачи симплексным методом
Запишем систему в векторной форме
х1*А1+х2*А2+х3*А3+х4*А4+х5*А5=Ао, где
Составляем симплексную таблицу.
|
i | Базис | Сбаз | Ао | С1=2 | С2=4 | С3=0 | С4=0 | С5=0 | С.О. | |
| | | | А1 | А2 | А3 | А4 | А5 | | |
1 | А3 | 0 | 425 | 11 | 10 | 1 | 0 | 0 | 42,5 | |
2 | А4 | 0 | 450 | 7 | 5 | 0 | 1 | 0 | 90 | |
3 | А5 | 0 | 550 | 8 | 6 | 0 | 0 | 1 | 91,66667 | |
m+1 | Zj-Cj | 0 | -2 | -4 | 0 | 0 | 0 | | |
|
Среди полученных оценок имеются две отрицательные: Z1-C1=-2<0 и Z2-C2=-4<0. Это означает, что первоначальный опорный план не является оптимальным и его можно улучшить, включив в базис вектор, которому соответствует максимальное по модулю отрицательное число в m+1 строке. Разрешающий вектор-столбец А2. Разрешающий элемент находим по минимальному симплексному отношению. Разрешающий элемент - число 10.
Составим вторую симплексную таблицу.
|
i | Базис | Сбаз | Ао | С1=2 | С2=4 | С3=0 | С4=0 | С5=0 | |
| | | | А1 | А2 | А3 | А4 | А5 | |
1 | А2 | 4 | 42,5 | 1,1 | 1 | 0,1 | 0 | 0 | |
2 | А4 | 0 | 237,5 | 1,5 | 0 | -0,5 | 1 | 0 | |
3 | А5 | 0 | 295 | 1,4 | 0 | -0,6 | 0 | 1 | |
m+1 | Zj-Cj | 170 | 2,4 | 0 | 0,4 | 0 | 0 | |
|
Просмотрев m+1 строку, убеждаемся, что опорный план - оптимален.
Оптимальный план предусматривает изготовление 42,5 ед.изделия В и не предусматривает изготовление изделий А. Изготовление изделий А привело бы к уменьшению прибыли на 2,4 у.е. Сырье 1-го вида используется полностью. Неиспользованными остается 450-237,5=212,5 тонн 2-го вида и 550-295=255 тонн 3-го вида сырья. Максимальная прибыль составляет 170 у.е.
Решение задачи на компьютере
Выполним следующие действия:
- В ячейку А1 вводим формулу для целевой функции=2*х1+4*х2
- В ячейку А3 вводим формулу для ограничения: =11*с1+10*с2.
- В ячейку А4 вводим формулу для ограничения: =7*с1+5*с2.
- В ячейку А3 вводим формулу для ограничения: =8*с1+6*с2.
- В ячейку С1:С2 вводим начальные значения переменных (0:0).
-Выполним команду Сервис > Поиск решения.
Следовательно, план выпуска продукции, включающий изготовление 42,5 изделий В является оптимальным. При данном плане выпуска изделий полностью используется сырье 1-го вида и остаётся неиспользованным 450-237,5=212,5 тонн 2-го вида и 550-295=255 тонн 3-го вида сырья, а стоимость производимой продукции равна 170 у.е.
ЛАБОРАТОРНАЯ РАБОТА №3
по мат.программированию
«Транспортная задача»
Имеются 3 пункта поставки однородного груза А1, А2, А3 и 5 пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1-А3 находится груз соответственно в количестве а1-а3 тонн. В пункты В1-В5 требуется доставить соответственно в1-в5 тонн груза. Стоимости перевозок 1 тонны груза между пунктами поставки и пунктами потребления приведены в матрице D. Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы общие затраты по перевозкам были минимальными.
|
Пункты поставки | Пункты потребления | Запасы | |
| В1 | В2 | В3 | В4 | В5 | | |
А1 | 12 | 10 | 15 | 12 | 13 | 350 | |
А2 | 16 | 14 | 17 | 10 | 8 | 150 | |
А3 | 15 | 10 | 13 | 14 | 15 | 280 | |
Потребн. | 100 | 120 | 200 | 160 | 200 | | |
|
Математическая модель задачи
Математическая модель транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений
при которых целевая функция
F=12*x11+10*x12+15*x13+12*x14+13*x15+16*x21+14*x22+17*x23+10*x24+8*x25+15*x31+10*x32+13*x33+14*x34+15*x35
принимает минимальное значение.
Опорный план найдем методом северо-западного угла.
|
Пункты поставки | Пункты потребления | Запасы | |
| В1 | В2 | В3 | В4 | В5 | | |
А1 | | | | | | 350 | |
А2 | | | | | | 150 | |
А3 | | | | | | 280 | |
Потребн. | 100 | 120 | 200 | 160 | 200 | | |
|
Для проверки плана на оптимальность необходимо построить систему потенциалов. Для построения системы потенциалов используем условие Ui+Vj=Cij
|
Пункты поставки | | Пункты потребления | Запасы | |
| | В1 | В2 | В3 | В4 | В5 | | |
| Потенциалы | V1= | V2= | V3= | V4= | V5= | | |
А1 | U1= | | | | | | 350 | |
А2 | U2= | | | | | | 150 | |
А3 | U3= | | | | | | 280 | |
Потребн. | | 100 | 120 | 200 | 160 | 200 | | |
|
|
Пункты поставки | | Пункты потребления | Запасы | |
| | В1 | В2 | В3 | В4 | В5 | | |
| Потенциалы | V1= | V2= | V3= | V4= | V5= | | |
А1 | U1= | | | | | | 350 | |
А2 | U2= | | | | | | 150 | |
А3 | U3= | | | | | | 280 | |
Потребн. | | 100 | 120 | 200 | 160 | 200 | | |
|
|
Пункты поставки | | Пункты потребления | Запасы | |
| | В1 | В2 | В3 | В4 | В5 | | |
| Потенциалы | V1= | V2= | V3= | V4= | V5= | | |
А1 | U1= | | | | | | 350 | |
А2 | U2= | | | | | | 150 | |
А3 | U3= | | | | | | 280 | |
Потребн. | | 100 | 120 | 200 | 160 | 200 | | |
|
|
Пункты поставки | | Пункты потребления | Запасы | |
| | В1 | В2 | В3 | В4 | В5 | | |
| Потенциалы | V1= | V2= | V3= | V4= | V5= | | |
А1 | U1= | | | | | | 350 | |
А2 | U2= | | | | | | 150 | |
А3 | U3= | | | | | | 280 | |
Потребн. | | 100 | 120 | 200 | 160 | 200 | | |
|
|
Пункты поставки | | Пункты потребления | Запасы | |
| | В1 | В2 | В3 | В4 | В5 | | |
| Потенциалы | V1= | V2= | V3= | V4= | V5= | | |
А1 | U1= | | | | | | 350 | |
А2 | U2= | | | | | | 150 | |
А3 | U3= | | | | | | 280 | |
Потребн. | | 100 | 120 | 200 | 160 | 200 | | |
|
|
Пункты поставки | | Пункты потребления | Запасы | |
| | В1 | В2 | В3 | В4 | В5 | | |
| Потенциалы | V1=7 | V2=5 | V3=8 | V4=7 | V5=8 | | |
А1 | U1=5 | 100 | 40 | | 160 | 50 | 350 | |
А2 | U2=0 | | | | | 150 | 150 | |
А3 | U3=5 | | 80 | 200 | | | 280 | |
Потребн. | | 100 | 120 | 200 | 160 | 200 | | |
|
Все незанятые клетки удовлетворяют условию Ui+Vj<=Cij.
Общая стоимость плана составляет
S=100*12+40*10+12*160+13*50+8*150+10*80+13*200=8770 у.е.
Решение задачи на компьютере
|
Объём перевозок | | | | | | |
12 | 10 | 15 | 12 | 13 | | | |
16 | 14 | 17 | 10 | 8 | | | |
15 | 10 | 13 | 14 | 15 | | | |
Объём перевозок | | | | Всего поставлено | |
100 | 40 | 0 | 160 | 50 | 350 | | |
0 | 0 | 0 | 0 | 150 | 150 | | |
0 | 80 | 200 | 0 | 0 | 280 | | |
100 | 120 | 200 | 160 | 200 | Всего получено | |
Затраты на перевозки | | | | | |
1200 | 400 | 0 | 1920 | 650 | | | |
0 | 0 | 0 | 0 | 1200 | | | |
0 | 800 | 2600 | 0 | 0 | | 8770 | |
|
|
Microsoft Excel 10.0 Отчет по результатам | | |
Рабочий лист: [Книга1]Лист2 | | |
Отчет создан: 17.12.2004 9:44:11 | | |
| | | | | |
Целевая ячейка (Минимум) | | | |
| Ячейка | Имя | Исходное значение | Результат | |
| $G$13 | | 0 | 8770 | |
| | | | | |
Изменяемые ячейки | | | |
| Ячейка | Имя | Исходное значение | Результат | |
| $A$6 | Объём перевозок | 0 | 100 | |
| $B$6 | | 0 | 40 | |
| $C$6 | | 0 | 0 | |
| $D$6 | | 0 | 160 | |
| $E$6 | | 0 | 50 | |
| $A$7 | Объём перевозок | 0 | 0 | |
| $B$7 | | 0 | 0 | |
| $C$7 | | 0 | 0 | |
| $D$7 | | 0 | 0 | |
| $E$7 | | 0 | 150 | |
| $A$8 | Объём перевозок | 0 | 0 | |
| $B$8 | | 0 | 80 | |
| $C$8 | | 0 | 200 | |
| $D$8 | | 0 | 0 | |
| $E$8 | | 0 | 0 | |
|