Решение задач симплексным методом

 

Вариант 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) соответственно.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы:

  1. Кузнецов, А.В. Руководство к решению задач по математическому программированию: Учеб. пособие / А.В. Кузнецов, Н.И. Холод, Л.С. Костевич; под общ. ред. А.В. Кузнецова. – Мн.: Вышэйшая школа, 2001. – 448 с.
  2. Фомин Г.П. Математические методы и модели в коммерческой деятельности / Фомин Г.П. - Финансы и статистика, 2005 г.- 616 стр.

 

 

 

 

 

 

 

 

 

 

 


Решение задач симплексным методом