Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

Данное решение является оптимальным.

Изобразим это решение на графике:

(2)
F
(4)
(1)
(3)
X ( оп)
X ( 2)
X ( 3)
X (4 )
Видим, что единственное и достигается в угловой точке области допустимых решений. 2 вариант.

Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же пива и в таких же пропорциях, за исключением того, что вместо пива «Премьер» было куплено пиво «Окское», крепость которого 6,4 % (дешевое и разбавленное). Определить план распития напитков для получения максимального суммарного опьянения (в Функция цели: Приводим ограничения к каноническому виду: = > Решаем симплекс-методом:

16 6,4 0 0 0 0
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 В
0 X 3 2 2 1 0 0 0 1,5
0 X 4 3,5 1 0 1 0 0 1,5
0 X 5 10 4 0 0 1 0 4,5
0 X 6 0 1 0 0 0 1 0,7
F -16 -10 0 0 0 0 0
16 6,4 0 0 0 0
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 В
0 X 3 0 1,428 1 -0,571 0 0 0,642
16 X 1 1 1,286 0 0,286 0 0 0,428
0 X 5 0 1,142 0 -2,85 1 0 0,214
0 X 6 0 1 0 0 0 1 0,7
F 0 -1,82 0 4,571 0 0 6,857
16 6,4 0 0 0 0
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 В
0 X 3 0 0 1 3 -1,25 0 0,375
16 X 1 1 0 0 1 -0,25 0 0,375
6,4 X 2 0 1 0 -2,5 0,875 0 0,1875
0 X 6 0 0 0 2,5 -0,875 1 0,5125
F 0 0 0 0 1,6 0 7,2
Видим, что все оценки положительны, значит оптимальное решение достигнуто. Но одна из свободных переменных (
16 10 0 0 0 0
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 в
0 X 4 0 0 0,333 1 -0,416 0 0,125
16 X 1 1 0 -0,333 0 0,166 0 0,25
10 X 2 0 1 1,833 0 -0,166 0 0,5
0 X 6 0 0 -0,833 0 0,166 1 0,2
F 0 0 0 0 1 0 7,2
Если оптимальное решение достигнуто в 2-х точках, то оно достигается и на отрезке между ними. Можно составить уравнение данного отрезка по формуле: ;
(2)
F,(3)
(4)
(1)
X ( оп)
X ( 2)
X ( 3)
X (4 )
На графике видно, что оптимальное решение достигается на отрезке, значит является альтернативным.

Вектор градиента целевой функции ( F) параллелен радиус-вектору ограничения ( 3 ). Это ограничение образует все множество оптимальных решений. Можно сделать вывод, что альтернативные решения имеются, когда все оценки свободных переменных больше 0, а среди коэффициентов целевой функции оценка одной из свободных переменных равна 0. 3 вариант.

Студент Петров, решив догнать по количеству выпитого студента Сидорова, выпил 4 доли пива «Русич» вместо запланированных 3,5. Решим задачу с учетом изменившихся данных.

Функция цели: Приводим ограничения к каноническому виду: = > Решим задачу симплекс-методом.

16 10 0 0 0 0
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 в
0 X 3 2 2 1 0 0 0 1,5
0 X 4 4 1 0 1 0 0 1,5
0 X 5 10 4 0 0 1 0 4,5
0 X 6 0 1 0 0 0 1 0,7
F -16 -10 0 0 0 0 0
.
16 10 0 0 0 0
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 В
0 X 3 0 1,5 1 -0,5 0 0 0,75
16 X 1 1 0,25 0 0,25 0 0 0,375
0 X 5 0 1,5 0 -2,5 1 0 0,75
0 X 6 0 1 0 0 0 1 0,7
F 0 -6 0 4 0 0 6
.
16 10 0 0 0 0
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 в
10 X 2 0 1 1,666 -0,333 0 0 0,5
16 X 1 1 0 -0,166 0,333 0 0 0,25
0 X 5 0 0 -1 -2 1 0 0
0 X 6 0 0 -0,666 0,333 0 1 0,2
F 0 0 4 2 0 0 9
Данное оптимальное решение является вырожденным, т.к. положительных компонентов меньше числа ограничений. На существование вырожденного оптимального решения указывает наличие в симплекс-таблице нулевого свободного члена при найденном оптимальном решении. В случае вырожденного решения симплекс-таблица может зацикливаться.

Существует 2 способа предупреждения зацикливания: а) – изменение хода ограничения на некоторые величины б) Если минимальное отношение свободных коэффициентов к положительным членам разрешающего столбца определяется неоднозначно, то выбирается отношение любого другого столбца к положительным коэффициентам данного столбца, пока строка не определится однозначно.

(1)
(4)
(2)
(3)
F
X (оп )
X ( 1)
X ( 2)
4 вариант. В связи с неожиданно полученной стипендией, запасы пива резко увеличились.

Функция цели: Приводим ограничения к каноническому виду: = > В матрице условий нет единичной подматрицы, поэтому используем метод искусственного базиса.

Построим вспомогательную задачу. Решаем вспомогательную задачу симплекс-методом:

0 0 0 0 0 0 1 1 1 1
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 в
1 X 7 2 2 -1 0 0 0 1 0 0 0 1,5
1 X 8 3.5 1 0 -1 0 0 0 1 0 0 1,5
1 X 9 10 4 0 0 -1 0 0 0 1 0 4,5
1 X 10 0 1 0 0 0 -1 0 0 0 1 0,7
F 15,5 8 -1 -1 -1 -1 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 в
1 X 7 0 1,428 -1 0,571 0 0 1 -0,571 0 0 0,642
0 X 1 1 0,285 0 -0,285 0 0 0 0,285 0 0 0,428
1 X 9 0 1,142 0 2,857 -1 0 0 -2,85 1 0 0,214
1 X 10 0 1 0 0 0 -1 0 0 0 1 0,7
F 0 3.571 -1 3,428 -1 -1 0 -4,42 0 0 1,557
0 0 0 0 0 0 1 1 1 1
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 в
1 X 7 0 0 -1 -3 1,25 0 1 3 -1,25 0 0,375
0 X 1 1 0 0 -1 0,25 0 0 1 -0,25 0 0,375
0 X 2 0 1 0 2,5 -0,875 0 0 -2,5 0,875 0 0,187
1 X 10 0 0 0 -2,5 0,875 -1 0 2,5 -0,875 1 0,512
F 0 0 -1 -5,5 2,125 -1 0 4,5 -3,12 0 0,887
0 0 0 0 0 0 1 1 1 1
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 в
1 X 8 0 0 -0,333 -1 0,416 0 0,333 1 -0,416 0 0,125
0 X 1 1 0 0,333 0 -0,166 0 -,333 0 0,166 0 0,25
0 X 2 0 1 -0,833 0 0,166 0 0,833 0 -0,166 0 0,5
1 X 10 0 0 0,833 0 -0,166 -1 -0,833 0 0,166 1 0,2
F 0 0 0,5 -1 0,25 -1 -1,5 0 -1,25 0 0,325
0 0 0 0 0 0 1 1 1 1
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 в
1 X 8 0 0 0 -1 0,35 -0,4 0 1 -0,35 0,4 0,205
0 X 1 1 0 0 0 -0,1 0,4 0 0 0,1 -0,4 0,17
0 X 2 0 1 0 0 0 -1 0 0 0 1 0,7
0 X 3 0 0 1 0 -0,2 -1,2 -1 0 0,2 1,2 0,24
F 0 0 0 -1 0,35 -0,4 -1 0 -1,35 -0,6 0,205
0 0 0 0 0 0 1 1 1 1
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 в
0 X 5 0 0 0 -2,85 1 -1,14 0 2,857 -1 -1,142 0,585
0 X 1 1 0 0 -0,285 0 0,285 0 0,285 0 -0,285 0,228
0 X 2 0 1 0 0 0 -1 0 0 0 1 0,7
0 X 3 0 0 1 -0,571 0 -1,42 -1 -1,571 0 1,428 0,357
F 0 0 0 0 0 0 -1 -1 -1 -1 0
оптимальное решение вспомогательной задачи.

Искусственные переменные являются свободными и равны нулю. Т.о. это решение является опорным планом исходной задачи. Решим исходную задачу:

16 10 0 0 0 0
С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 в
0 X 5 0 0 0 -2,85 1 -1,14 0,585
16 X 1 1 0 0 -0,285 0 0,285 0,228
10 X 2 0 1 0 0 0 -1 0,7
0 X 3 0 0 1 -0,571 0 -1,42 0,357
F 0 0 0 -4,576 0 -5,424 3,648
(1)
(4)
(2)
(3)
F
X (оп )
5 вариант. После отмеченного таким образом праздника обязательно наступает похмелье. Решим задачу из предыдущего варианта, минимизируя этот неприятный фактор, т.е. функция цели: Приводим ограничения к каноническому виду: = > Эта задача решается методом искусственного базиса, т.к. в ней нет единичной подматрицы.

Разное

Подобные работы

Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

echo "Данное решение является оптимальным. Изобразим это решение на графике: (2) F (4) (1) (3) X ( оп) X ( 2) X ( 3) X (4 ) "; echo ''; ech

Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ)

echo "Требуется выбрать города, в которых можно получить максимальную прибыль от продажи спиртного. При этом суммарное расстояние от этих портов до порта с грузом не должно превышать 1000 миль. 2. Реш

Лабораторная работа №4 по "Основам теории систем" (Послеоптимизационный анализ задач линейного программирования)

echo "Оптимальные двойственные оценки "; echo ''; echo " Теперь найдём область устойчивости двойственных оценок к изменению свободных членов ограничений. Как известно, область устойчивости двойственны

Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)

echo "Запишем оптимальное решение: "; echo ''; echo " и оптимальное значение целевой функции: "; echo ''; echo " Экономически полученное решение интерпретируется следующим образом: для получения едини

"Принцип Максимума" Понтрягина

echo "Иногда рассматривают и более широкие классы допустимых управлений, например, класс всех ограниченных измеримых управлений, удовлетворяющих условию (1.2). Покажем, как при произвольном начальном

Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

echo "Считая что "; echo ''; echo " "; echo ''; echo " "; echo ''; echo " "; echo ''; echo " количество мышей, проживающих в "; echo ''; echo " "; echo ''; echo " "; echo ''; echo " 1) "; echo ''; ech

Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

echo "Сказано – сделано. Спрыгнул колобок из окошка и покатился в лес. Помогите колобку найти кратчайший маршрут его движения по лесу, если расстояния между норами лесных жителей, а также домом деда