Главная Учебники - Разные Лекции (разные) - часть 50
Телешовой
Елизаветы, гр.
726,
Цель работы:
Решение
задач линейного
программирования
симплекс-методом.
Варианты разрешимости
задач линейного
программирования.
1 вариант.
1. Четыре студента:
Иванов, Петров,
Сидоров и Васильев
пошли на концерт
группы «Чайф»,
захватив пиво
2 сортов: «Русич»
и «Премьер».
Определить
план распития
напитков для
получения
максимального
суммарного
опьянения (в
Запасы
(в литрах)
2. Математическая
модель.
2.1 Управляемые
параметры
x1[л]
– количество
выпитого пива
«Русич».
x2[л]
– количество
выпитого пива
«Премьер».
2.2 Ограничения
Общее количество
пива, выпитого
Ивановым, не
превосходит
имеющихся у
него запасов
пива, поэтому:
Аналогично
строим другие
ограничения:
3. Постановка
задачи.
Найти
4. Решение.
Приведем
задачу к каноническому
виду:
Определим
начальный
опорный план:
Это решение
является опорным,
т.к. вектора
условий при
положительных
компонентах
решения линейно
независимы,
также
Опорный план
является оптимальным,
если для задачи
максимизации
все его оценки
неотрицательны.
Предположим,
что
Запишем новый
опорный план:
При увеличении
Из ограничения
(2)
имеем:
Подставляя
в функцию цели:
Оформим данный
этап задачи
в виде симплекс-таблицы:
Начальная
симплекс-таблица: X1 X2 X3 X4 X5 X6 X3 X4 X5 X6
Пересчитаем
элементы исходной
таблицы по
правилу четырехугольника: X1 X2 X3 X4 X5 X6 X3 X1 X5 X6
Пересчитав
все оценки,
видим, что
откуда получаем:
Все оценки
опорного плана
должны быть
неотрицательны,
а значит должны
выполняться
условия:
Выведем из
базиса
X1 X2 X3 X4 X5 X6 X3 X1 X2 X6
Пересчитав
все оценки,
видим, что
откуда получаем:
Все оценки
опорного плана
должны быть
неотрицательны,
а значит должны
выполняться
условия:
Выведем из
базиса
Св X1 X2 X3 X4 X5 X6 X4 X1 X2 X6
Видим, что
все оценки
положительны,
значит любое
увеличение
какой-либо
свободной
переменной
уменьшит критерий.
Данное решение
является оптимальным.
Изобразим это
решение на
графике:
Видим, что
2 вариант.
Отмечая
успешно сданную
сессию, вышеупомянутые
студенты взяли
столько же пива
и в таких же
пропорциях,
за исключением
того, что вместо
пива «Премьер»
было куплено
пиво «Окское»,
крепость которого
6,4 % (дешевое и
разбавленное).
Определить
план распития
напитков для
получения
максимального
суммарного
опьянения (в
Функция цели:
Приводим
ограничения
к каноническому
виду:
Решаем
симплекс-методом: X1 X2 X3 X4 X5 X6 X3 X4 X5 X6
X1 X2 X3 X4 X5 X6 X3 X1 X5 X6
Св X1 X2 X3 X4 X5 X6 X3 X1 X2 X6
Видим, что
все оценки
положительны,
значит оптимальное
решение достигнуто.
Но одна из свободных
переменных
( Св X1 X2 X3 X4 X5 X6 X4 X1 X2 X6
Если оптимальное
решение достигнуто
в 2-х точках, то
оно достигается
и на отрезке
между ними.
Можно составить
уравнение
данного отрезка
по формуле:
На графике
видно, что
оптимальное
решение достигается
на отрезке,
значит является
альтернативным.
Вектор градиента
целевой функции
(F) параллелен
радиус-вектору
ограничения
(3). Это ограничение
образует все
множество
оптимальных
решений.
Можно сделать
вывод, что
альтернативные
решения имеются,
когда все оценки
свободных
переменных
больше 0, а среди
коэффициентов
целевой функции
оценка одной
из свободных
переменных
равна 0.
3 вариант.
Студент
Петров, решив
догнать по
количеству
выпитого студента
Сидорова, выпил
4 доли пива «Русич»
вместо запланированных
3,5. Решим задачу
с учетом изменившихся
данных.
Функция
цели:
Приводим
ограничения
к каноническому
виду:
Решим задачу
симплекс-методом. X1 X2 X3 X4 X5 X6 X3 X4 X5 X6
X1 X2 X3 X4 X5 X6 X3 X1 X5 X6
Св X1 X2 X3 X4 X5 X6 X2 X1 X5 X6
Данное оптимальное
решение является
вырожденным,
т.к. положительных
компонентов
меньше числа
ограничений.
На существование
вырожденного
оптимального
решения указывает
наличие в
симплекс-таблице
нулевого свободного
члена при найденном
оптимальном
решении.
В случае
вырожденного
решения симплекс-таблица
может зацикливаться.
Существует
2 способа предупреждения
зацикливания:
а)
б) Если минимальное
отношение
свободных
коэффициентов
к положительным
членам разрешающего
столбца определяется
неоднозначно,
то выбирается
отношение
любого другого
столбца к
положительным
коэффициентам
данного столбца,
пока строка
не определится
однозначно.
4
вариант.
В связи с
неожиданно
полученной
стипендией,
запасы пива
резко увеличились.
Функция цели:
Приводим
ограничения
к каноническому
виду:
В матрице
условий нет
единичной
подматрицы,
поэтому используем
метод искусственного
базиса. Построим
вспомогательную
задачу.
Решаем
вспомогательную
задачу симплекс-методом: X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X7 X8 X9 X10 X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X7 X1 X9 X10 X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X7 X1 X2 X10 X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X8 X1 X2 |