Решение задач симплексным методом
Вариант 19.
Задание 1.
На предприятии имеется 400 тыс. литров алкилата, 250 тыс. литров крекинг-бензина, 350 тыс. литров бензина прямой перегонки и 100 тыс. литров изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуется три сорта авиационного бензина: А — 2:3:5:2, бензина Б — 4:1:2:1 и бензина С — 2:2:1:3. Стоимость 1 тыс. литров бензина А равна 110 у.д.е., бензина Б — 100 у.д.е., бензина С — 150 у.д.е. Определить план смешивания компонентов, при котором будет достигнута максимальная стоимость всей продукции.
Решение:
Введем следующие обозначения:
i – индекс вида сырья;
m – количество видов сырья;
j – индекс вида бензина;
n – количество видов бензина;
хj – количество тысяч литров бензина j-го вида,
aij – затраты сырья i-го вида на производство бензина j-го вида;
Сj – стоимость одной тысячи литров бензина j-го вида;
Bi – располагаемое количество сырья i-го вида.
В принятых обозначениях математическая модель задачи имеет следующий вид:
При следующих ограничениях:
Если раскрыть знаки сумм и проставить значения индексов, то математическая модель задачи будет иметь вид:
При ограничениях:
Подставив численные значения используемых величин, получим следующую математическую модель задачи:
При ограничениях:
Решаем задачу симплекс-методом.
Приведем систему ограничений из симметрического вида к каноническому. Добавим дополнительные неотрицательные переменные .
Система ограничений имеет базисный вид. Переменные x4, x5, x6, x7 являются базисными, а остальные x1, x2, x3 – свободными.
Строим 1-ю симплексную таблицу.
В – свободные коэффициенты.
Найдем свободные коэффициенты для x4, x5, x6, x7.
Приравняем x1 = 0, x2 = 0, x3 = 0
СБ – коэффициенты в целевой функции.
Баз. пер. |
СБ |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
110 |
100 |
150 |
0 |
0 |
0 |
0 | |||
x4 |
0 |
400 |
2 |
4 |
2 |
1 |
0 |
0 |
0 |
x5 |
0 |
250 |
3 |
1 |
2 |
0 |
1 |
0 |
0 |
x6 |
0 |
350 |
5 |
2 |
1 |
0 |
0 |
1 |
0 |
x7 |
0 |
100 |
2 |
1 |
3 |
0 |
0 |
0 |
1 |
Z |
0 |
-110 |
-100 |
-150 |
0 |
0 |
0 |
0 | |
Нахождение Z:
Последняя строчка таблицы используется для определения оптимального плана.
Критерий оптимальности плаза задачи на максимум: если в последней строке симплексной таблицы задачи на максимум все элементы положительны, то план оптимален.
Наш план не оптимален, т.к. в последней строке есть отрицательные числа.
Для изменения плана выбираем разрешающий столбец, который соответствует наименьшему из отрицательных чисел последней строки. Этот столбец показывает, какую переменную необходимо ввести в базис. В нашем случае это x3
Переменная, которую нужно убрать из базиса определяется разрешающей строкой.
Для разрешающего столбца составляют симплексные отношения ().
Симплексные отношения –
отношения элементов из столбца
«В» к соответствующим
Так строка, в которой достигается наименьшее отношение, называется разрешающей.
Разрешающая строка указывает, какую переменную необходимо убрать из базиса. У нас это x7.
Для определения нового плана необходимо пересчитать все числовые значения таблицы в последней схеме.
Элемент, стоящий на пересечении разрешающей строки и столбца, называется разрешающим (выделен красным цветом).
1) Разрешающая строка
делится на разрешающий
2) В новой таблице на остальные ячейки разрешающего столбца записываются нули.
3) Остальные элементы
пересчитываются по правилу
Баз. пер. |
СБ |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
110 |
100 |
150 |
0 |
0 |
0 |
0 | |||
x4 |
0 |
1000/3 |
2/3 |
10/3 |
0 |
1 |
0 |
0 |
-2/3 |
x5 |
0 |
550/3 |
5/3 |
1/3 |
0 |
0 |
1 |
0 |
-2/3 |
x6 |
0 |
950/3 |
13/3 |
5/3 |
0 |
0 |
0 |
1 |
-1/3 |
x3 |
150 |
100/3 |
2/3 |
1/3 |
1 |
0 |
0 |
0 |
1/3 |
Z |
5000 |
-10 |
-50 |
0 |
0 |
0 |
0 |
50 | |
Т.к. в последней строке есть отрицательные числа, план не оптимальный.
Баз. пер. |
СБ |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
110 |
100 |
150 |
0 |
0 |
0 |
0 | |||
x2 |
100 |
100 |
1/5 |
1 |
0 |
3/10 |
0 |
0 |
-1/5 |
x5 |
0 |
150 |
8/5 |
0 |
0 |
-1/10 |
1 |
0 |
-3/5 |
x6 |
0 |
150 |
4 |
0 |
0 |
-1/2 |
0 |
1 |
0 |
x3 |
150 |
0 |
3/5 |
0 |
1 |
-1/10 |
0 |
0 |
2/5 |
Z |
10000 |
0 |
0 |
0 |
15 |
0 |
0 |
40 | |
В последней строке нет отрицательных чисел, план является оптимальным.
Оптимальный план можно записать так:
Таким образом, для получения максимального дохода в 10 000 у.д.е. необходимо производить из имеющегося сырья 100 тысяч литров бензина Б, а бензин А и С не производить.
Ответ:
Задание 2.
Магазин может закупить для реализации а, в или с единиц скоропортящегося товара по цене d у.д.е. за единицу товара. В зависимости от состояния спроса на данный товар (пониженный, умеренный или повышенный) может быть продано в день реализации соответственно а, в или с единиц товара по цене p у.д.е. за 1 товара. Остаток товара реализуется полностью на следующий день по сниженной цене t у.д.е. за 1 товара. Дополнительная закупка товара осуществляется по цене s у.д.е. Какую стратегию закупок использовать магазину, чтобы максимизировать доход, при а=20, в=30, с=40, d=3, р=5, t=1, s = 4 и =0,5.
Решение:
В рассматриваемой ситуации в качестве игрока А выступает магазин, обладающий 3-мя возможными стратегиями: А1 – закупить 20 ед. скоропортящегося товара, А2 – 30, А3 – 40.
Цена закупки единицы товара – 3 у.д.е., цена дополнительной закупки единицы товара – 4 у.д.е. Цена реализации единицы товара – 5 у.д.е., цена реализации единицы остатка товара – 1 у.д.е.
Неопределенность ситуации связана с потребительским спросом.
Итак, находим каждый элемент матрицы:
1. Магазин решил применить стратегию А1 (т.е. закупить 20 ед. товара). При П1 (пониженный спрос - 20 ед. товара)
расходы магазина будут равняться: - 3 * 20 = -60
прибыль будет равна: а11 = 20 * 5 - 60 = 40 у.д.е.
При П2 (умеренный спрос – 30 ед. товара) магазину не хватит заказанного товара, поэтому придется дополнительно закупить 10 ед. Дополнительные расходы придется вычесть из прибыли.
а12 = 30 * 5 – 20* 3 – 10* 4 = 50 у.д.е.
При П3 – а13 = 40 * 5 – 20* 3 – 20* 4 = 60 у.д.е.
2. Магазин решил применить стратегию А2 (т.е. закупить 30 ед. товара). При П1 (пониженный спрос - 20 ед. товара) магазин реализует только 20 ед. товара по цене 5 у.д.е., остаток товара будет реализован на следующий день по сниженной цене 1 у.д.е. за единицу товара.
а21 = 20 * 5 + 10 * 1 – 30* 3 = 20 у.д.е.
Считаем дальше по аналогии:
а22 = 30 * 5 – 30* 3 = 60 у.д.е.
а23 = 40 * 5 – 30* 3 – 10* 4 = 70 у.д.е.
Стратегия А3 (закупить 40 ед. товара):
а31 = 20 * 5 + 20 * 1 – 40* 3 = 0 у.д.е.
а32 = 30 * 5 + 10 * 1 – 40* 3 = 40 у.д.е.
а33 = 40 * 5 – 40* 3 = 80 у.д.е.
Платежная матрица будет выглядеть следующим образом:
Пj
Аi |
П1 |
П2 |
П3 |
|
|
А1 |
40 |
50 |
60 |
40 |
А2 |
20 |
60 |
70 |
20 |
А3 |
0 |
40 |
80 |
0 |
40 |
60 |
80 |
I. Критерий Вальда
За оптимальную принимается та стратегия, которая в наихудших условиях гарантирует максимальный выигрыш.
, что соответствует стратегии А1.
По критерию Вальда следует закупать 20 единиц товара.
II. Критерий Сэвиджа
За оптимальную принимается
та стратегия, при которой величина
максимального риска
где (максимальный элемент j-ом столбце платёжной матрицы, берем из предыдущей платежной матрицы).
Пj
Аi |
П1 |
П2 |
П3 |
|
|
А1 |
0 |
10 |
20 |
20 |
А2 |
20 |
0 |
10 |
20 |
А3 |
40 |
20 |
0 |
40 |
, что соответствует стратегии А1 и А2.
По критерию Сэвиджа фирме следует закупать 20 или 30 единиц товара.
III. Критерий Гурвица
За оптимальную принимается та стратегия, для которой выполняется соотношение
Пj
Аi |
П1 |
П2 |
П3 |
||
|
А1 |
40 |
50 |
60 |
40 |
60 |
А2 |
20 |
60 |
70 |
20 |
70 |
А3 |
0 |
40 |
80 |
0 |
80 |
что соответствует стратегии А1.
По критерию Гурвица следует закупать 20 единиц товара.
Задание 3.
Построить сетевой график выполнения комплекса работ по реконструкции цеха по данным таблицы 79 и рассчитать — временные параметры событий и работ сетевого графика.
Таблица 79 — Исходные данные
Решение:
При построении сетевого графика мы соблюдали следующие правила.
1 В сетевой модели не
должно быть событий, из
2 В сетевом графике не должно быть событий (кроме исходного), которым не предшествует хотя бы одна работа.
3 В сети не должно быть замкнутых контуров и петель, т.е. путей, соединяющих некоторые события с ними же самими.
4 Любые два события должны быть непосредственно связаны не более, чем одной работой.
5 Сетевой график должен быть полностью упорядоченным. Упорядочение сетевого графика заключается в таком расположении событий и работ, при котором для любой работы предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием.
Итак, рассмотрим параметры событий.
Ранний (или ожидаемый) срок tp(i) свершения i-го события:
Поздний (или предельный) срок tn(i) свершения i-го события равен:
Резерв времени R(i) i-го события определяется как разность между поздним и ранним сроками его свершения:
Расположение временных параметров непосредственно на сетевом графике.
Определим временные параметры событий и критический путь для нашего сетевого графика. Результаты расчета временных параметров фиксируем на графике.
При определении ранних сроков
свершения событий tp(i)
двигаемся по сетевому графику слева направо
и используем формулу
Для i=1 (первого события). Очевидно tp(i) =0.
Для i = 2: tp (2) = tp (1) + t(1,2) = 0 + 1 = 1 (день), т.к. для события 2 существует только один предшествующий путь1 2.
Для i = 3: tp (3) = max{tp (1) + t(1,3); tp (2) + t(2,3)}=max{0+2; 1+0}=max{2; 1}=2 (дня), т.к. для события 3 существует два предшествующих пути 1 3, 2 3.
Для i = 4: tp (4)=max{tp (1) + t(1,4); tp (3) + t(3,4)}=max{0+3; 2+1}=max{3; 3}=3 (дня), т.к. для события 4 существует два предшествующих пути 1 4, 3 4.
Аналогично рассчитаем ранние
сроки свершения остальных
Длина критического пути равна раннему сроку свершении завершающего события 7: tkp=tp(7) = 8 (дней).
При определении поздних
сроков свершения событий tn (i) двигаемся
по сети в обратном направлении, т.е. справа
налево и используем формулу
Для i=7 (завершающего события) поздний срок свершения события должен быть равен его раннему сроку (иначе изменится длина критического пути): tn (7) = tp(7) = 8 (дней).
Для i = 6: tn (6) = tn (7) – t (6,7) = 8 – 2 = 6 (дней), так как для события 6 существует только один последующий путь 6 7.
Для i = 5: tn (5) = tn (7) – t(5,7) = 8 – 1 = 7 (дней), так как для события 5 существует только один последующий путь 5 7.
Для i=4: tn (4) = min{ tn (6) – t(4,6); tn (7) – t(4,7) ; tn (5) – t(4,5)} = min{6 – 2; 8 – 3; 7 – 4} = min{4; 5; 3} = 3 (дня), т.к. для события 4 существует три последующих пути 4 6, 4 7, 4 5.
Аналогично рассчитаем поздние
сроки свершения остальных
По формуле определим резервы времени i-го события:
R(1) = 0; R(2) = 2 – 1 = 1 и т.д.
Резерв времени события 2 - R(2) = 1 — означает, что время свершения события 2 может быть задержано на один день без увеличения общего срока выполнения проекта. Анализируя сетевой график с временными параметрами, видим, что все события 1, 3, 4, 5, 7 не имеют резервов времени. Они образуют критический путь (выделен жирной линией на графике).
Рассмотрим параметры работ.
Ранний срок tрн(i,j) начала работы (i,j) совпадает с ранним сроком наступления предшествующего события i, т.е.
Ранний срок tро, окончания работы (i,j):
Поздний срок tnо(i,j) окончания работы (i,j) определяется:
Поздний срок tnн(i,j) начала этой работы соотношением
Среди резервов времени работ выделяют четыре их разновидности.
Полный резерв времени Rn(i,j) работы (i,j):
Частный резерв времени первого вида R1(i,j) работы (i,j):
Частный резерв времени второго вида, или свободный резерв времени Rс(i,j) работы (i,j):
Независимый резерв времени Rп работы (i,j):
Вычисление временных параметров работы (i,j) покажем на примере работы (2,5):
- ранний срок начала работы tрн(2,5) = tр(2) = 1 (день);
- ранний срок окончания работы: tро(2,5) = tр(2) + t(2,5) = 1 + 3 = 4 (дня);
- поздний срок начала работы: tпн(2,5) = tп(5) - t (2,5) = 7 - 3 = 4 (дня);
- поздний срок окончания работы: tпо(2,5) = tп(5)= 7 (дней).
Таким образом, работа (2,5) должна начаться в интервале [1;4] (дней) от начала выполнения проекта.
Полный резерв работы (2,5):
Rn(2,5) = tп(5) - tp(2) - t(2,5) = 7-1-3 = 3 (дня), т.е. срок выполнения данной работы можно увеличить на три дня, при этом срок выполнения комплекса работ не изменится.
Частный резерв времени работы (2,5) первого вида:
R1(2,5) = tп(5) – tп(2) - t(2,5) = 7-2-3 = 2 (дня), т.е. при сохранении общего срока выполнения проекта выполнение работы (2,5) может быть задержано на 2 дня без затрат резерва времени предшествующих ей работ.
Частный резерв времени второго вида, или свободный резерв времени, работы (2,5) найдем:
Rс(2,5) = tр(5) – tр(2) - t(2,5) = 7-1-3 = 3 (дня), т.е. при сохранении общего срока выполнения проекта выполнение работы (2,5) может быть задержано на 3 дня без нарушения резерва времени последующих работ.
Независимый резерв времени работы (2,5):
Rн(2,5) = tр(5) – tп(2) - t(2,5) = 7-2-3 = 2 (дня).
Рассчитываем также остальные
резервы и заносим результаты
расчетов в таблицу. Подчеркнем, что
резервы критических работ
Работа (i,j) |
Продолжительность работы t (i,j) |
Сроки начала и окончания работы |
Резервы времени работы | ||||||
tрн (i,j) |
tро (i,j) |
tпн (i,j) |
tпо (i,j) |
Rn (i,j) |
R1 (i,j) |
Rc (i,j) |
Rн (i,j) | ||
(1,2) |
1 |
0 |
1 |
1 |
2 |
1 |
1 |
0 |
0 |
(1,3) |
2 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
0 |
(1,4) |
3 |
0 |
3 |
0 |
3 |
0 |
0 |
0 |
0 |
(2,5) |
3 |
1 |
4 |
4 |
7 |
3 |
2 |
3 |
2 |
(3,4) |
1 |
2 |
3 |
2 |
3 |
0 |
0 |
0 |
0 |
(3,5) |
4 |
2 |
6 |
3 |
7 |
1 |
1 |
1 |
1 |
(4,5) |
4 |
3 |
7 |
3 |
7 |
0 |
0 |
0 |
0 |
(4,6) |
2 |
3 |
5 |
4 |
6 |
1 |
1 |
0 |
0 |
(4,7) |
3 |
3 |
6 |
5 |
8 |
2 |
2 |
2 |
2 |
(5,7) |
1 |
7 |
8 |
7 |
8 |
0 |
0 |
0 |
0 |
(6,7) |
2 |
5 |
7 |
6 |
8 |
1 |
0 |
1 |
0 |
Исходя из расчетов, у нас получилось 2 варианта критического пути; в зависимости от того, какую работу мы совершим вначале (1,3) или (1,4), критический путь будет проходить через (1,3), (3,4), (4,5), (5,7) или через (1,4), (4,5), (5,7) соответственно.
Список использованной литературы:
- Кузнецов, А.В. Руководство к решению задач по математическому программированию: Учеб. пособие / А.В. Кузнецов, Н.И. Холод, Л.С. Костевич; под общ. ред. А.В. Кузнецова. – Мн.: Вышэйшая школа, 2001. – 448 с.
- Фомин Г.П. Математические методы и модели в коммерческой деятельности / Фомин Г.П. - Финансы и статистика, 2005 г.- 616 стр.