4.4.1. Словесная формулировка задачи. Для производства четырех видов изделий A1, A2, A3, A4 завод должен использовать три вида сырья I, II, III, запасы которого на планируемый период составляют соответственно 200, 600 и 150 условных единиц. В приведенной ниже таблице даны технологические коэффициенты, т. е. расход каждого вида сырья на производство единицы каждого изделия, и прибыль от реализации единицы изделий каждого вида (ден. ед.).
| Вид | Запасы | Технологические коэффициенты | |||
| сырья | сырья | A1 | A2 | A3 | A4 |
| I | |||||
| II | |||||
| III | |||||
| Прибыль от реализации |
Необходимо: а) составить такой план выпуска указанных изделий, чтобы обеспечить максимальную прибыль от их реализации; б) найти оптимальное решение прямой и двойственной задач, провести анализ на устойчивость; в) определить изменение максимальной прибыли при изменении запасов сырья: I вида — на -20, II— на -10, III— на +10 единиц. Оценить раздельное и суммарное влияние этих изменений на величину максимальной прибыли; г) оценить целесообразность введения в план пятого вида продукции А5, нормы затрат сырья на единицу которого соответственно равны 2, 4, 2, а прибыль равна 12; д) оценить целесообразность закупки 50 единиц ресурса III вида по цене c3 = 0.5.
4.4.2. Анализ словесной формулировки. В задаче требуется составить план выпуска изделий, поэтому в качестве неизвестных модели целесообразно выбрать объемы выпуска изделий (ед.): xi – объем выпуска изделий вида A i, i=1,2,3,4. По смыслу xi не могут принимать отрицательных значений.
Цель задачи состоит в максимизации прибыли от реализации изделий. Зная объем выпуска, прибыль от реализации единицы продукции каждого вида, заключаем, что суммарная прибыль составит
|
|
(ден. ед.).
Запасы используемого сырья ограничены, поэтому надо знать расход сырья каждого вида при заданном плане производства. Принимая во внимание технологические коэффициенты, заключаем, что расход первого ресурса на все виды продукции составит
(усл. ед.),
второго —
(усл. ед.),
третьего —
(усл. ед.).
4.4.3. Математическая формулировка задачи. Исходя из предварительного анализа модели, запишем математическую модель в виде задачи линейного программирования:
максимизировать общую прибыль F=6x1+x2+10x3+2x4
при ограничениях
x1, x2, x3, x4 ³ 0.
Составим двойственную задачу:
Z=200y1 + 600y2 + 150y3 ® min
при ограничениях
|
y1, y2, y3 ³ 0.
4.4.4. Распечатки результатов. Решая задачу обычным симплекс-методом (программа SM_RV), сохраним на диске следующие результаты:
оптимальная симплекс-таблица
17/02/96 00:21:22
Заключительная итеpация
B[1;1] = 1.5000000000E+02
B[1;2] = 0.0000000000E+00
B[1;3] = 1.0000000000E+00
B[1;4] = 0.0000000000E+00
B[1;5] = 6.0000000000E+00
B[1;6] = 3.0000000000E+00
B[1;7] =-1.0000000000E+00
B[1;8] = 1.0000000000E+00
B[2;1] = 5.0000000000E+01
B[2;2] = 1.0000000000E+00
B[2;3] = 0.0000000000E+00
B[2;4] = 0.0000000000E+00
B[2;5] =-4.0000000000E+00
B[2;6] =-2.0000000000E+00
B[2;7] = 1.0000000000E+00
B[2;8] =-1.0000000000E+00
B[3;1] = 5.0000000000E+01
B[3;2] = 0.0000000000E+00
B[3;3] = 0.0000000000E+00
B[3;4] = 1.0000000000E+00
B[3;5] = 2.5000000000E+00
B[3;6] = 1.0000000000E+00
B[3;7] =-5.0000000000E-01
B[3;8] = 1.0000000000E+00
B[4;1] = 9.5000000000E+02
B[4;2] = 0.0000000000E+00
B[4;3] = 0.0000000000E+00
B[4;4] = 0.0000000000E+00
B[4;5] = 5.0000000000E+00
B[4;6] = 1.0000000000E+00
B[4;7] = 0.0000000000E+00
B[4;8] = 5.0000000000E+00
Окончательный результат
17/02/96 00:21:56 SM_RV
Zmax = 9.50000000E+02
X[2] = 1.5000000000E+02 Res = 0.000E+00 M[1] = 0.00000000E+00
X[1] = 5.0000000000E+01 Res = 2.328E–10 M[2] = 0.00000000E+00
|
|
X[3] = 5.0000000000E+01 Res = 0.000E+00 M[3] = 0.00000000E+00
M[4] = 5.00000000E+00
M[5] = 1.00000000E+00
M[6] = 0.00000000E+00
M[7] = 5.00000000E+00
Те же расчеты проделаем с помощью модифицированного симплекс-метода (программа MODSM_RV). При этом можно использовать матрицу исходных данных, сохраненную в предыдущих расчетах.
оптимальная симплекс-таблица
17/02/96 01:18:37
Заключительная итеpация
B[1;1] = 5.0000000000E+01
B[1;2] = 1.0000000000E+00
B[1;3] =-5.0000000000E-01
B[1;4] = 1.0000000000E+00
B[2;1] = 1.5000000000E+02
B[2;2] = 3.0000000000E+00
B[2;3] =-1.0000000000E+00
B[2;4] = 1.0000000000E+00
B[3;1] = 5.0000000000E+01
B[3;2] =-2.0000000000E+00
B[3;3] = 1.0000000000E+00
B[3;4] =-1.0000000000E+00
B[4;1] = 9.5000000000E+02
B[4;2] = 1.0000000000E+00
B[4;3] = 0.0000000000E+00
B[4;4] = 5.0000000000E+00
Окончательный результат
17/02/96 01:19:17 MODSM_RV
Zmax = 9.50000000E+02
X[3] = 5.0000000000E+01 Res = 0.000E+00 M[1] = 0.00000000E+00
X[2] = 1.5000000000E+02 Res = 0.000E+00 M[2] = 0.00000000E+00
X[1] = 5.0000000000E+01 Res = 0.000E+00 M[3] = 0.00000000E+00
M[4] = 5.00000000E+00
M[5] = 1.00000000E+00
M[6] = 0.00000000E+00
M[7] = 5.00000000E+00
Решение двойственной задачи с помощью ПЭВМ приводит к следующим результатам:
18/02/96 11:35:12 SM_RV
Zmin = 9.50000000E+02
| X[7] = 5.0000000000E+00 | Res = 0.000E+00 | M[1] = 0.00000000E+00 | |
| X[1] = 1.0000000000E+00 | Res = 1.819E–12 | M[2] = 2.50000000E+02 | |
| X[4] = 3.6379788071E–12 | Res =–1.455E–11 | M[3] = 0.00000000E+00 | |
| X[3] = 5.0000000000E+00 | Res = 0.000E+00 | M[4] = 0.00000000E+00 | |
| M[5] = 2.00000000E+02 | |||
| M[6] = 7.50000000E+01 | |||
| M[7] = 0.00000000E+00 | |||
| M[8] = 0.00000000E+00 | |||
| M[9] =–2.00000000E+02 | |||
| M[10] =–7.50000000E+01 | |||
| M[11] = 0.00000000E+00 |
18/02/96 11:34:03 MODSM_RV
Zmin = 9.50000000E+02
| X[7] = 5.0000000000E+00 | Res = –7.276E–12 | M[1] = 0.00000000E+00 | |
| X[1] = 1.0000000000E+00 | Res = 0.000E+00 | M[2] = 2.50000000E+02 | |
| X[4] = 9.0949470177E–13 | Res =–1.455E–11 | M[3] = 0.00000000E+00 | |
| X[3] = 5.0000000000E+00 | Res = –7.276E–12 | M[4] = 0.00000000E+00 | |
| M[5] = 2.00000000E+02 | |||
| M[6] = 7.50000000E+01 | |||
| M[7] = 0.00000000E+00 | |||
| M[8] = 1.00000000E+00 | |||
| M[9] = 1.00000000E+00 | |||
| M[10] = 1.00000000E+00 | |||
| M[11] = 1.00000000E+00 |
|
|
Отметим, что специфика задачи об ограниченных ресурсах позволяет получать решение двойственной задачи непосредственно из распечатки результатов прямой задачи. В общем случае построение двойственного решения требует дополнительных вычислений. Например, чтобы по результатам решения двойственной задачи нашего примера восстановить решение исходной задачи, необходимо иметь коэффициенты при базисных переменных в целевой функции после исключения искусственных переменных (нахождения начального допустимого опорного плана), а их можно получить с помощью программы SM_RV в режиме просмотра промежуточных результатов.
|
Часто пользователям проще решить отдельно прямую и двойственную задачи, чем восстанавливать решение одной по решению другой. Вместе с тем, некоторые коммерческие пакеты не только решают задачу линейного программирования, но и проводят анализ полученного решения.
4.4.5. Сравнение результатов и выводы. В результате решения задачи на ПЭВМ с использованием разных методов вычислений получен один и тот же результат с незначительной погрешностью (о точности результата можно судить по значениям невязок, которые представляют собой разности между правой и левой частями ограничений в стандартной модели со всеми дополнительными переменными после того, как туда подставлено полученное решение - значения базисных переменных.
Полученное решение можно расшифровать так: для получения наибольшей прибыли, равной 950 денежным единицам, предприятие должно выпустить 50 ед. продукции вида A1, 150 ед. продукции вида A2, 50 ед. продукции вида A3. Продукцию вида A4 в данных условиях производить невыгодно.
4.4.6. Анализ на чувствительность. Выпишем матрицу коэффициентов при базисных переменных (x3, x2, x1) в исходной симплекс-таблице:
.
Перед выводом окончательного результата программа MODSM_RV выдает окончательную симплекс–таблицу (она же распечатана ранее поэлементно):
| B[1,1] = 5.0000000000E+01 410528 11:06:53 | ||||||||
| Столбец 1 Пpосмотp массива Столбцов 4 | ||||||||
| С | 50.0000 | 1.0000 | –0.5000 | 1.0000 | С | |||
| т | 150.0000 | 3.0000 | –1.0000 | 1.0000 | т | |||
| р | 50.0000 | –2.0000 | 1.0000 | –1.0000 | р | |||
| о | 950.0000 | 1.0000 | 0.0000 | 5.0000 | о | |||
| к | к | |||||||
| а | ||||||||
| F1Помощь F2Сохp.F3Печ.F4Идти к F5Инф. PgDn® Esc Дальше Alt-X Выход |
Из этой симплекс-таблицы выписываем матрицу, обратную к матрице B, которая имеет вид:
.
Запишем оптимальное решение двойственной задачи:
.
Как показывает величина оценок, наиболее дефицитным является ресурс III, так как y3* =5, а наименее дефицитным – ресурс I, так как y1* =1. Ресурс II используется полностью, так как остаточная переменная x6*=0, но увеличение его запаса не улучшит значения целевой функции, так как y2* = 0. Выпишем полученные результаты в таблицу:
| Ресурс | Статус ресурса | Теневая цена | Остаток ресурса |
| I | дефицитный | ||
| II | недефицитный | ||
| III | дефицитный |
Чтобы эффективно оценивать изменение максимальной прибыли при изменении запасов ресурсов, необходимо найти промежутки устойчивости двойственных оценок.
Относительно первого ресурса, получаем
.
Для второго и третьего ресурсов
,
.
Находим соответствующие колебания максимальной прибыли.
Результаты вычислений сведем в таблицу
| Ресурс | Запас | Промежуток устойчивости двойственных оценок | Колебания максимальной прибыли |
| I | [150; 225] | [900; 975] | |
| II | [550; 700] | [950; 950] | |
| III | [100; 200] | [700; 1200] |
Поскольку заданные по условию изменения запасов ресурсов удовлетворяют правилу 100%, суммарное влияние изменения запасов ресурсов на прибыль вычисляем как сумму раздельных влияний:
;
.
Исследуем границы изменения удельной прибыли от реализации продукции, в пределах которых оптимальное решение (план производства) остается неизменным. При этом будем использовать оптимальную симплекс-таблицу, полученную при применении программы SM_RV. Для базисных переменных (x1, x2, x3) получаем:
,
,
.
Для небазисной переменной x4 имеем:
, то есть 
.
Результаты вычислений сведем в таблицу:
| Вид продукции | Удельная прибыль | Промежуток устойчивости оптимума |
| A1 | [6; 6.5] | |
| A2 | 
| |
| A3 | [9; 10] | |
| A4 | [-¥; 7] |
Оценим целесообразность введения в план пятого вида продукции A5. Для этого вычислим характеристику
.
Так как D5 = 0, то вводить пятый вид продукции нецелесообразно, однако, если добиться даже незначительного увеличения прибыли c5, производство пятого вида продукции станет прибыльным делом.
Приращение третьего ресурса на 50 усл. ед. находится в пределах устойчивости двойственных оценок. Учитывая, что реальная стоимость ресурса (0.5 ден. ед.) меньше теневой цены, приходим к выводу о целесообразности закупки ресурса вида III в количестве 50 усл. ед. по цене 0.5 ден. ед.
|
Расчетные задания для
Лабораторной работы №1
Всюду далее N – номер варианта студента, соответствующий его порядковому номеру по списку группы.
Варианты 1 – 6. В производстве двух видов продукции A и B последовательно участвуют три предприятия. Пpи этом на изготовление единицы пpодукции A пеpвое предприятие тpатит N часов, втоpое пpедпpиятие –3N часов, третье,– 2N часов. Hа изготовление единицы изделия B пеpвое предпpиятие тpатит 3N часов, втоpое пpедпpиятие – 2N часов, тpетье – N часов. Hа пpоизводство всех изделий пеpвое пpедпpиятие может затpатить не более чем 100N часов, втоpое пpедпpиятие – не более чем 160N часов, тpетье – не более чем 120N часов. От единицы готовой пpодукции вида A пpибыль составит (N+3) pублей, B – (N+2) pублей. Пpи каком объеме пpоизводства пpибыль будет максимальной?
Ваpианты 7 – 12. В отделе технического контpоля (ОТК) некотоpой фиpмы pаботают контpолеpы pазpядов 1 и 2. Hоpма выpаботки ОТК за 8‑часовой pабочий день составит не менее 2400 изделий. Контpолеp 1‑го pазpяда пpовеpяет 25 изделий в час, пpичем не ошибается В 98% случаев. Контpолеp 2‑го pазpяда пpовеpяет 20 изделий в час, пpичем не ошибается в 95% случаев. Заpаботная плата контpолеpа pазpяда 1 pавна 400 pублей в час. Заpаботная плата контpолеpа pазpяда 2 pавна 300 pублей в час. Пpи каждой ошибке фиpма несет убыток в pазмеpе 200 pублей. Фиpма может использовать (N– 5)´4 контpолеpов pазpяда 1 и (N–6) ´5 контpолеpов pазpяда 2. Руководство фиpмы хочет опpеделить оптимальный состав ОТК, пpи котоpом общие затpаты на контpоль будут минимальными.
Ваpианты 13 – 18. Для пpоизводства двух видов пpодукции пpедпpиятие использует 2 типа технологического обоpудования и 2 вида сыpья. Hоpмы затpат сыpья и вpемени на изготовление одного изделия каждого вида пpиведены в таблице. В ней же указаны общий фонд pабочего вpемени каждой из гpупп технологического обоpудования, объемы имеющегося сыpья каждого вида, а также цена одного изделия данного вида. Составить такой план пpоизводства пpодукции, согласно котоpому будет изготовлено необходимое количество изделий каждого вида пpи максимальной общей стоимости изготовляемой пpодукции.
| Ресурсы | Нормы затрат на одно изделие вида | Общее количество | |
| ресурсов | |||
| Производительность оборудования (нормо-час): | |||
| I типа | — | ||
| II типа | |||
| Сырье (кг): | |||
| 1-го вида | |||
| 2-го вида | |||
| Цена 1-го изделия (руб) | 10´N | 8´N | — |
Ваpианты 19-24. Фиpма выпускает два пpодукта: A и B. Hоpмы затpат сыpья и вpемени на изготовление единицы пpодукта каждого вида, а также пpибыль от pеализации готовой пpодукции пpиведены в таблице. Опpеделить наиболее доходный пpоизводственный план.
| Ресурсы | Нормы затрат на единицу продукта | Общее количество ресурсов | |
| A | B | ||
| Сырье | |||
| Труд ИТР | |||
| Физ. труд | |||
| Прибыль | N | N–1 | – |
Ваpианты 25–30. Пpедпpиятие электpонной пpомышленности выпускает две модели pадиопpиемников, пpичем каждая модель пpоизводится на отдельной технологической линии. Максимальный суточный объем пpоизводства пеpвой линии 60 изделий, втоpой линии 75 изделий. Hа pадиопpиемник пеpвой модели pасходуется 10 однотипных элементов электpонных схем. Hа pадиопpиемник втоpой модели – 8 таких же элементов. Максимальный суточный запас используемых элементов pавен 800 единицам. Пpибыли от pеализации одного пpиемника пеpвой и втоpой модели pавны N-15 и N-20 тыс. pублей соответственно. Опpеделите оптимальные суточные объемы пpоизводства 1 и 2 модели так, чтобы пpибыль была максимальной.