Итерация 4
Шаг 1
Выписываем исходное допустимое базисное решение, то есть первый план перевозок и вычисляем соответствующее ему значение целевой функции.
250 0 370
0 500 200
Х4 = 250 0 0
120 0 0
0 0 130
Z4 = 5*250 + 4*370 + 2*500 + 2*200 + 4*250 + 2*120=5370
Шаг 2.
Проверяем план на оптимальность.
С1,2 = 90+4 (+) С2,3 = 3-2+5 (+) С3,2 = 6-1+4 (+)
С3,3 = 5-1+4 (+) С4,2= 5-3+4 (+) С4,3 = 3-3+4 (+)
С5,1 = 0-4+5 (-) С5,2 = 0-4+4 (+)
Вывод: так как не для всех пустых клеток выполняется соотношение
Cij Ui + Vj (*), то план представленный в транспортной схеме 5 не оптимальный, его нужно улучшить.
Шаг 3
Выполнение процесса улучшение плана.
Для этого определим из какого карьера, на какую стройплощадку произведется перепоставка и ее величину (то есть определим какая из прежних базисных неизвестных должна быть выведена из базиса). Клетки в которых не выполняется соотношение (*) – плохие, из всех них выбираем только одну, в данном случае это клетка С5,1.
Процесс улучшения плана выполняем в соответствии с правилом замкнутого маршрута, по которому происходит перераспределение поставок и улучшение ранее построенного плана: маршрут замкнут, то есть начинается с плохой клетки и в ней же заканчивается.
Шаг 4.
Строим новый план с намеченными на шаге 3 изменениями и занесем результаты в транспортную схему 6 (таблица 2.8).
Таблица 2.8 Транспортная схема 6
Карьеры |
Стройплощадки |
Сумма запасов |
Ui |
||
1 |
2 |
3 |
|||
1 |
120 5 |
9 |
500 4 |
620 |
0 |
2 |
3 |
500 2 |
200 2 |
700 |
-2 |
3 |
250 4 |
6 |
5 |
250 |
-1 |
4 |
120 2 |
5 |
3 |
120 |
-3 |
5 |
130 0 |
0 |
0 |
130 |
-5 |
Сумма потребностей |
620 |
500 |
700 |
1820 |
|
Vj |
5 |
4 |
4 |
|
5240 |
Итерация 5
Шаг 1
Выписываем исходное допустимое базисное решение, то есть первый план перевозок и вычисляем соответствующее ему значение целевой функции.
120 0 500
0 500 200
Х4 = 250 0 0
120 0 0
130 0 0
Z4 = 5*120 + 4*500 + 2*500 + 2*200 + 4*250 + 2*120=5240
Шаг 2.
Проверяем план на оптимальность.
С1,2 = 90+4 (+) С2,1 = 3-2+5 (+) С3,2 = 6-1+4 (+)
С3,3 = 5-1+4 (+) С4,2= 5-3+4 (+) С4,3 = 3-3+4 (+)
С5,2 = 0-5+4 (+) С5,3 = 0-5+4 (+)
Вывод: так как для всех пустых клеток выполняется соотношение
Cij Ui + Vj (*), то план представленный в транспортной схеме 6 оптимальный.
Анализ решения задачи:
Z= 5240
120 0 500
0 500 200
Х = 250 0 0
120 0 0
130 0 0
Следовательно, оптимальный план перевозок следующий:
С первого карьера на первую стройплощадку гравия необходимо отвезти 120 тонн, на третью – 500 тонн; со второго карьера на вторую стройплощадку необходимо отвезти гравия 500 тонн, на третью – 200 тонн; с третьего карьера на первую стройплощадку – 250 тонн гравия; с четвертого карьера на первую стройплощадку – 120 тонн гравия и с пятого карьера на первую стройплощадку – 130 тонн. Весь гравий вывезен. При этом минимальные грузоперевозки составляют 5240 т/км.
Задача 3
5.1. Решим игру аналитически:
Max (min) =max (21; 22) =22
Min (max) =min (70; 49) =49
α =22; β =49
Так как
α
β , то отсюда следует, что седловой точки
нет и игра решается в смешанных стратегиях.
22 γ 49
А – игрок 1, В – игрок 2.
=>
70 (1-
)
+ 21
= 22 (1-
)
+ 49
70 - 70 + 21 = 22 - 22 + 49
-49 -27 = 22 -70
-76 = -48
=
=
1-
=
-
оптимальная стратегия первой компании
А
=>
-48
=-31
= 0,63
= 0,37
- оптимальная стратегия второй компании
В
Средняя величина прибыли при любом
состоянии спроса равна 39 денежных единиц
объема выпуска каждой модели. Смешанная
стратегия первой компании
,
смешанная стратегия второй компании
.
5.2. Решим игру сведением к задаче линейного программирования.
Составим пару взаимно двойственных задач:
(1)
f =
+
max (2) f =
min
Приведем задачу к каноническому виду:
f=
+
+0*
+0*
max
строим
симплексную таблицу:
Шаг 0 |
|
|
|
|
|
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x3 |
1 |
70 |
21 |
1 |
0 |
x4 |
1 |
22 |
49 |
0 |
1 |
ИС |
0 |
-1 |
-1 |
0 |
0 |
Шаг 1 |
|
|
|
|
|
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x1 |
1/70 |
1 |
3/10 |
1/70 |
0 |
x4 |
24/35 |
0 |
212/5 |
-11/35 |
1 |
ИС |
1/70 |
0 |
-7/10 |
1/70 |
0 |
Шаг 2 |
|
|
|
|
|
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x1 |
1/106 |
1 |
0 |
7/424 |
-3/424 |
x2 |
6/371 |
0 |
1 |
-11/1484 |
5/212 |
ИС |
19/742 |
0 |
0 |
27/2968 |
7/424 |
Решение игры:
5.3.
переменные |
||||||
имя |
Х1 |
Х2 |
|
|
|
|
Значение |
0,009434 |
0,016173 |
ЦФ |
Направл. |
|
|
ЦФ |
1 |
1 |
0,025606 |
max |
|
|
|
|
|
|
|
|
|
ограничения |
||||||
вид |
|
|
лев часть |
знак |
прав часть |
|
Огран.1 |
70 |
21 |
1 |
<= |
1 |
|
Огран.2 |
22 |
49 |
1 |
<= |
1 |
|
5.4. Все найденные решения одинаковы.
5.5.Чтобы компании получили среднюю прибыль равную 39 рублей, фирма А должна рекламировать 36% своего товара по радио и 64 % в газетах, фирма В 37% на телевидении и 63 % рассылает брошюры по почте.
5.6. Решение задачи аналитически, в симплексе и в Excel дает одинаковый результат. Делаем вывод, что задача решена правильно.
5.7.
Отчет по результатам |
|
|
|
|||
Целевая ячейка (Максимум) |
|
|
|
|
||
|
Ячейка |
Имя |
Исходное значение |
Результат |
|
|
|
$D$4 |
ЦФ ЦФ |
0 |
0,025606469 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Изменяемые ячейки |
|
|
|
|
||
|
Ячейка |
Имя |
Исходное значение |
Результат |
|
|
|
$B$3 |
Значение Х1 |
0 |
0,009433962 |
|
|
|
$C$3 |
Значение Х2 |
0 |
0,016172507 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ограничения |
|
|
|
|
||
|
Ячейка |
Имя |
Значение |
Формула |
Статус |
Разница |
|
$D$8 |
Огран.1 лев часть |
1 |
$D$8<=$F$8 |
связанное |
0 |
|
$D$9 |
Огран.2 лев часть |
1 |
$D$9<=$F$9 |
связанное |
0 |
Отчет по устойчивости |
|
|
|
||||
Изменяемые ячейки |
|
|
|
|
|
||
|
|
|
Результ. |
Нормир. |
Целевой |
Допустимое |
Допустимое |
|
Ячейка |
Имя |
значение |
стоимость |
Коэффициент |
Увеличение |
Уменьшение |
|
$B$3 |
Значение Х1 |
0,009433962 |
0 |
1 |
2,333333333 |
0,551020408 |
|
$C$3 |
Значение Х2 |
0,016172507 |
0 |
1 |
1,227272727 |
0,7 |
|
|
|
|
|
|
|
|
Ограничения |
|
|
|
|
|
||
|
|
|
Результ. |
Теневая |
Ограничение |
Допустимое |
Допустимое |
|
Ячейка |
Имя |
значение |
Цена |
Правая часть |
Увеличение |
Уменьшение |
|
$D$8 |
Огран.1 лев часть |
1 |
0,009097035 |
1 |
2,181818182 |
0,571428571 |
|
$D$9 |
Огран.2 лев часть |
1 |
0,016509434 |
1 |
1,333333333 |
0,685714286 |
Отчет по пределам |
|
|
|
|
|||||
|
|
Целевое |
|
|
|
|
|
|
|
|
Ячейка |
Имя |
Значение |
|
|
|
|
|
|
|
$D$4 |
ЦФ ЦФ |
0,025606469 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Изменяемое |
|
|
Нижний |
Целевой |
|
Верхний |
Целевой |
|
Ячейка |
Имя |
Значение |
|
предел |
результат |
|
предел |
результат |
|
$B$3 |
Значение Х1 |
0,009433962 |
|
0 |
0,016172507 |
|
0,009433962 |
0,025606469 |
|
$C$3 |
Значение Х2 |
0,016172507 |
|
0 |
0,009433962 |
|
0,016172507 |
0,025606469 |