Жолобов Ввведение в Математическое 2008
.pdf
|
700x1 1400x2 30x3 40x4 100x5 |
max |
||||||||
|
|
2x1 |
6x2 |
x3 |
100000 |
|
||||
|
|
|
||||||||
|
|
x1 |
x2 |
x4 |
70000 |
|
||||
|
|
|
||||||||
|
|
2x1 2x2 |
x5 |
80000 |
|
|||||
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
j |
0, ( j 1,5). |
|
||||
|
|
|
|
|
|
|
|
|
|
|
Решение |
|
|
|
|
|
|
|
|
|
|
Суммарная прибыль: |
32.7 млн руб. |
|
|
|
|
|||||
Выработка электроэнергии |
|
|
|
|
|
|||||
Э1: 35000 МВтч |
|
|
|
|
|
|
|
|
|
|
Э2: |
5000 МВтч |
|
|
|
|
|
|
|
|
|
Продажа сырья |
|
|
|
|
|
|
|
|
|
|
S1 : |
0 ед. |
|
|
|
|
|
|
|
|
|
S2 : |
30000 ед. |
|
|
|
|
|
|
|
|
|
S3 : |
0 ед. |
|
|
|
|
|
|
|
|
|
Заметим, что если продать все сырье, не вырабатывая электроэнергии, то будет получена прибыль:
100000 30+70000 40+80000 100=13.8 млн руб.
Пример 1.4
Условия примера 1.3 сохраняются, но предполагаем, что сырье можно докупать со стороны по ценам:
30 руб. – за единицу сырья вида S1;
50 руб. – за единицу сырья вида S2;
20 руб. – за единицу сырья вида S3.
При этом затраты на дополнительную покупку сырья не должны превышать 10 млн руб. Естественно, что если продажа сырья увеличи-
вает доход АЭС, то покупка – уменьшает доход.
11
x1 |
Э1 |
|
|
Э2 |
|
x2 |
|
|
|
|
|
|
|
10000 |
x3 |
|
S1 |
|
|
|
|
70000 |
x4 |
|
||
|
|||
|
S2 |
80000 x5 S3
|
|
x6 |
|
x7 |
|
x8 |
|
|
Математическая модель задачи: |
|
|
|
|
||||
700x1 1400x2 |
30x3 |
40x4 |
100x5 |
30x6 50x7 |
20x8 |
max |
||
|
2x1 |
6x2 |
x3 x6 |
|
100000 |
|
|
|
|
x1 |
x2 |
x4 |
x7 |
70000 |
|
|
|
|
2x1 2x2 |
x5 |
x8 |
|
80000 |
|
|
|
|
30x6 |
50x7 |
20x8 |
|
10000000 |
|
|
|
|
xj 0,( j 1,..,5). |
|
|
|
|
Решение
Суммарный доход: 83.33 млн руб.
Выработка электроэнергии
П1: 6666 МВтч П2: 63333 МВтч
Продажа сырья
S1 : 0 ед.
S2 : 0 ед.
S3 : 2 ед.
Покупка сырья
S1 : 293333 ед.
S2 : 0 ед.
S3 : 60000 ед.
Этот пример показателен с экономической точки зрения. Так, если ничего не производить, а взять, например, сырье S3 (покупка – по 20
руб. за ед.; продажа – по 100 руб.), то:
продажа всего запаса принесет доход 13.8 млн руб;
покупка на 10 млн руб. сырья S3 увеличит его запас на 500000 ед,
12
а последующая продажа по цене 100 руб. за ед. принесет доход 50 млн руб. Таким образом, доход от перепродажи составит 40 млн руб. Результирующий итог такой операции равен 13.8+40=53.8 млн руб.
Следовательно, в результате реализации простой спекуляционной сделки будет иметь место потеря в 83.3-53.8=29.53 млн руб.
Контрольные вопросы и задачи к разделу 1.1
1. Фирма выпускает три вида продукции (изделий). В процессе производства используются три технологические операции.
На рисунке показана технологическая схема производства.
Операция11 |
Операция 2 |
|
Операция 3 |
|
|
|
1 мин/изд |
|
3 мин/изд |
|
1 мин/изд |
|
Изделие 1(3р.) |
|
|
|
|
|
|
|
2 мин/изд |
|
|
|
4 мин/изд |
|
Изделие 2(2р.) |
|
|
|
|
|
|
|
1 мин/изд |
|
2 мин/изд |
|
|
|
Изделие 3(5р.) |
Операц430 миня 1 |
460 мин |
|
420 мин |
|
|
В прямоугольниках указана длительность технологических операций при изготовлении одного изделия каждого вида.
Фонд рабочего времени, в течение которого операции могут быть применены для производства рассматриваемых изделий, ограничен:
для первой операции – 430 мин, для второй операции – 460 мин, для третьей операции – 420 мин.
Изучение рынка сбыта показало, что ожидаемая прибыль от продажи одного изделия видов 1, 2 и 3 составляет 3, 2 и 5 тыс. руб. соответственно.
Каков наиболее выгодный суточный объем производства каждого вида продукции?
2. Компания, специализирующаяся на разработке инновационных средств радиационной защиты, получила заказ от государства на выпуск 20000 индивидуальных защитных костюмов. На производство одного костюма расходуется не менее одного килограмма материалов. К костюмам предъявляются требования по задержке внешнего радиоактивного излучения снаружи, сохранения температурного режима внутри костюма и проницаемости костюмов для
13
кислорода. Для производства костюмов как правило используется широкий перечень материалов. Мы же для простоты ограничимся только тремя: хлопком, инновационным наноматериалом, хорошо задерживающим радиацию и синтетической тканью. Также предположим пропорциональность характеристик материала его доле, содержащейся в костюме, и их аддитивность в случае комбинации материалов в костюме.
Данные по характеристикам каждого из трех материалов и их удельной стоимости сведем в таблицу 1.1.
|
|
|
|
Таблица 1.1 |
|
Материал |
|
Характеристики |
|
Стоимость |
|
Задержка |
Проницаемость |
Сохранение |
|||
руб./кг |
|||||
|
радиации |
для кислорода |
тепла |
|
|
Наноматериал |
100% |
10% |
70% |
2000 |
|
Синтетика |
80% |
10% |
85% |
800 |
|
Хлопок |
70% |
50% |
30% |
400 |
К костюму предъявляются следующие требования:
1)сохранение не менее 40% и не более 90% тепла организма;
2)пропускание не менее 20% кислорода;
3)задержка не менее 90% радиоактивного излучения. Необходимо определить количество (в килограммах) каждого
из трех материалов, которое необходимо приобрести для выполнения госзаказа на костюмы, обладающее минимальной стоимостью при условии, чтобы характеристики готовых изделий находились в требуемых диапазонах.
3. Промышленная фирма производит изделие, представляющее собой сборку из трех узлов. Эти узлы выпускаются на двух заводах.
Из-за различия в составе технологического оборудования производительность заводов по выпуску изделий каждого вида неодинакова.
В табл.1.2 содержатся исходные данные, характеризующие как производительность заводов по выпуску каждого из узлов, так и максимальный суммарный ресурс времени, которым в течение недели располагает каждый из заводов для производства этих узлов.
14
|
|
|
Таблица 1.2 |
|
Завод |
Максимальный недельный |
Производительность узел/ч |
||
|
фонд времени, ч |
Узел 1 |
Узел 2 |
Узел 3 |
1 |
100 |
8 |
5 |
10 |
2 |
80 |
6 |
12 |
4 |
Идеальной является ситуация, когда производственные мощности обоих заводов используются таким образом, что в итоге обеспечивается выпуск одинакового количества каждого из видов узлов. Однако этого трудно добиться из-за различий в производительности заводов.
Более реальная цель состоит в максимизации выпуска готовых изделий – это, по существу, эквивалентно минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или двум видам узлов.
Требуется определить еженедельные затраты времени (в часах) на производство каждого из трех узлов на каждом заводе (переменные), не превышающие в сумме временные ресурсы каждого завода (ограничения) и обеспечивающие максимальный выпуск изделий (целевая функция).
4. При изготовлении изделий двух видов осуществляется последовательная обработка соответствующих заготовок на двух различных станках.
Изделие 1
Изделие 2
Станок 1 |
Станок 2 |
Каждый станок может использоваться для производства изделий по 8 часов в сутки. Однако этот фонд может быть увеличен еще на 4 часа. Каждый час сверхурочных работ требует дополнительных расходов в размере 500 руб.
15
Производительность станков и прибыль в расчете на одно изделие приведены в таблице 1.3.
|
|
Таблица 1.3 |
|
Станок |
Производительность изд./час |
||
Изделие 1 |
Изделие 2 |
||
|
|||
1 |
5 |
6 |
|
2 |
4 |
8 |
|
Прибыль (руб./ед.) |
600 |
400 |
Требуется определить количество изделий каждого вида (переменные), которые нужно производить, чтобы максимизировать чистую прибыль (целевая функция), при условии, что время использования станков можно увеличить только за счет сверхурочных работ (ограничения).
1.2. Симплекс-метод
1.2.1.Виды задач линейного программирования
Влинейном программировании различают три основные формы задач.
Задача линейного программирования в общей форме имеет
вид:
n |
|
|
|
|
|
|
|
c j x j max |
|||||||
j 1 |
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
aij x j ai |
( i |
1, k |
) |
|
|||
j 1 |
|
(1.1) |
|||||
n |
|
|
|
|
|
|
|
aij x j ai |
(i |
k 1, m |
) |
||||
j 1 |
|
|
|
|
|
|
|
x j 0, |
(j |
|
, n1 n). |
||||
1, n1 |
Задача в стандартной (естественной, симметричной) фор-
ме:
n |
|
|
c j x j max |
|
|
j 1 |
|
|
n |
|
(1.2) |
aij x j ai |
(i 1, m) |
j 1
x j 0, (j 1, n).
16
или
n
c j x j min
j 1
n
aij x j ai (i 1, m)
j 1
x j 0, (j 1, n).
Задача в канонической форме:
n
c j x j max
j 1
n
aij x j ai (i 1, m)
j 1
(1.3)
(1.4)
x j 0, ( j 1, n).
Любой задаче линейного программирования можно придать любую из перечисленных форм, используя простейшие преобразования.
1.Изменение направления оптимизации
Исходная задача: |
Эквивалентная задача: |
n |
n |
c j x j min |
c j x j max |
j 1 |
j 1 |
Оптимальные решения исходной задачи и задачи, полученной в результате преобразования 1, будут совпадать, однако оптимальные значения целевых функций будут иметь противоположные знаки.
2.Придание ограничениям – нестрогим неравенствам противопо-
ложного направления |
|
Исходная задача: |
Эквивалентная задача: |
n |
n |
aij x j ai |
aij x j a j |
j 1 |
j 1 |
3.Наложение на переменные требования неотрицательности Исходная задача: Эквивалентная задача:
Замена переменной:
xj не ограничена в знаке .
17
xj = xj1-xj2 ; xj1,xj2 0.
4.Замена уравнений неравенствами |
|
|
Исходная задача: |
Эквивалентная задача: |
|
|
|
n |
n |
|
aij xj ai |
aij xj ai |
|
j 1 |
|
n |
|
i 1 |
|
|
|
aij xj ai |
|
|
|
j 1 |
5.Замена нестрогих неравенств уравнениями В этом преобразовании на каждое нестрогое неравенство вво-
дится "своя" переменная, которая называется дополнительной пе-
ременной. При этом возможны два случая. |
|
Случай 1 |
|
Исходная задача: |
Эквивалентная задача: |
|
|
n |
|
ai |
n |
aij xj xдопi |
|||
aij x j ai |
j 1 |
|
|
|
j 1 |
|
xi |
0 |
|
|
|
доп |
|
|
Случай 2 |
|
|
|
|
Исходная задача: |
Эквивалентная задача: |
|||
|
|
n |
|
ai |
n |
aij xj xдопi |
|||
aij x j ai |
j 1 |
|
|
|
j 1 |
|
xi |
0 |
|
|
|
доп |
|
|
Преобразование 2, по существу, является результатом трех |
||||
преобразований: |
|
|
|
|
Шаг 1. Изменение направления неравенства |
|
|
|
|
Исходная задача: |
Эквивалентная задача: |
|||
n |
n |
|
|
|
ai j x j ai |
ai j x j ai |
|
|
|
j 1 |
j 1 |
|
|
|
18
Шаг 2. Замена неравенства уравнением |
|
Исходная задача: |
Эквивалентная задача: |
|
|
|
|
|
|
|
|
|
n |
|
xдопi |
ai |
|||
|
|
n |
|
ai |
|
|
|
aij xj |
|||||||
ai j x j |
|
|
|
|
j 1 |
|
|
|
|
|
|||||
|
|
j 1 |
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xдоп 0 |
|
|
|
|
|
Шаг 3. Умножение на "-1" левой и правой части уравнения. |
|||||||||||||||
Исходная задача: |
|
|
|
Эквивалентная задача: |
|||||||||||
|
n |
|
|
ai |
|
|
|
|
n |
|
|
|
ai |
|
|
aij xj xдопi |
|
|
|
aij xj xдопi |
|
||||||||||
|
j 1 |
|
|
|
|
|
|
j 1 |
|
|
|
|
|
||
|
|
|
i |
|
|
|
|
|
i |
|
|
|
|
||
|
|
xдоп 0 |
|
|
|
|
|
xдоп 0 |
|
|
|||||
Пример 1.5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
Придать следующей задаче форму канонической: |
|
|
|
|
|
||||||||
|
|
|
|
z* |
2x |
|
14x |
18x |
|
7x |
|
min |
|||
|
|
|
|
|
1 |
|
2 |
|
3 |
|
4 |
|
|
|
|
|
|
|
|
|
4x1 |
|
20x2 |
|
4x3 |
|
8x4 |
|
|
200 |
|
|
|
|
|
|
x1 |
|
7x2 |
|
2x3 |
|
x4 |
|
|
130 |
|
|
|
|
|
|
4x1 |
2x2 |
4x3 |
|
5x4 |
|
|
|
90 |
||
|
|
|
|
|
xj 0, |
(j=1,2,3), x4 не ограничена в знаке. |
|
||||||||
|
|
Преобразование производится по следующей схеме: |
|
|
|
|
|||||||||
|
|
1.Наложение на переменную x4 |
требования неотрицательности путем |
||||||||||||
|
|
замены этой переменной разностью двух неотрицательных переменных: |
|||||||||||||
|
|
x4=x5-x6 |
(преобразование 3); |
|
|
|
|
|
|
|
|
||||
|
|
2.Изменение направления оптимизации (преобразование 1); |
|
||||||||||||
|
|
3.Замена нестрогих неравенств строгими равенствами (преобразование |
|||||||||||||
|
|
5): в первое ограничение вводится дополнительная переменная x7 , а во |
|||||||||||||
|
|
второе – переменная x8 . |
|
|
|
|
|
|
|
|
|
||||
|
|
|
В результате этих преобразований задача приобретает вид: |
||||||||||||
|
|
2x1 |
|
14x2 |
18x3 |
|
7x5 |
|
7x6 |
|
|
max |
|
||
|
|
4x1 |
|
20x2 |
|
4x3 |
|
8x5 |
|
8x6 |
+x7 |
|
200 |
|
|
|
|
x1 |
|
7x2 |
|
2x3 |
|
x5 |
|
x6 |
x8 |
|
130 |
|
|
|
|
4x1 |
|
2x2 |
|
4x3 |
|
5x5 |
|
5x6 |
|
|
|
90 |
|
|
|
|
|
|
|
xj 0 |
j=1 8. |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
Оптимальное решение этой задачи:
x1 82.2, x2 0, x3 0, x5 0, x6 47.8, x7 253.3, x8 0;
Zо*пт 499.
Оптимальное решение исходной задачи формируется следующим образом:
1.Изменяется знак оптимального значения целевой функции;
2.Отбрасываются дополнительные переменные x7 и x8 ;
3.Восстанавливается переменная x4=x5-x6.
Витоге имеем:
Xопт 82.2, |
0, 0, 47.8 ; |
Zопт 499. |
Задачи в форме канонической (1.4) и симметричной (1.2), (1.3) принято называть задачами с однотипными ограничениями. Для их исследования удобно использовать компактные формы за-
писи: матрично-векторную и векторную.
Эти формы рассмотрим на примере канонической задачи, которую приведем в развернутом виде:
c1x1 c2 x2 |
|
... cj xj |
... cn xn max |
|||
a11x1 a12 x2 |
... a1 j xj |
... |
a1n xn a1 |
|||
a21x1 a22 x2 |
... a2 j xj |
... |
a2n xn a2 |
|||
|
||||||
ai1x1 ai2 x2 |
... aij xj |
... |
ain xn ai |
|||
|
||||||
am1 x1 am 2 x2 ... amj x j ... amn xn am |
||||||
|
|
|
x j 0, (j = 1,.., n). |
|||
Примем следующие обозначения: |
|
|||||
c (c1 ,c2 ,...,cn ) |
– вектор коэффициентов целевой функции; |
|||||
x (x1 , x2 ,..., xn ) |
– вектор переменных задачи; |
|||||
a |
a |
|
... |
a |
|
|
11 |
12 |
|
1n |
|
||
A aij a21 |
a22 |
... |
a2n – матрица, составленная из ко- |
|||
... |
... |
... |
... |
|
||
|
am2 |
... |
|
|
||
am1 |
amn |
|
эффициентов левой части системы ограничений; 20