 |
|
АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология |
Пример решения задачи методом искусственного базисаРешим двухэтапным методом искусственного базиса задачу из раздела 1.3.1. Для этого ее надо вначале привести к канонической форме: min 4х1 + 15х2 + 40х3
380х1 + х2 + 2х3 + х5 = 6 90х2 + 50х3 – х6 = 110 20х2 + 80х3 + х7 = 25 х1 + х2 + х3 = 0,5 х1-7 ³ 0 Здесь дополнительная переменная х4 представляет собой превышение содержания кальция в рационе над минимально допустимым, а х5 показывает, на сколько оно ниже максимально допустимого. Переменная х6 показывает, на сколько содержание белка в рационе больше минимально допустимого, а х7 – на сколько меньше содержание клетчатки по сравнению с максимально допустимым. Все эти величины измеряются в граммах.
В этой задаче свободные члены неотрицательны. Имеется часть базиса, а именно единичные столбцы стоят при двух переменных – х5 и х7 (во втором и четвертом ограничениях). В остальных трех уравнениях базисных переменных нет, поэтому введем три искусственные переменные и построим расширенную задачу для реализации двухэтапного симплекс-метода следующим образом: min у1 + у2 + у3
380х1 + х2 + 2х3 + х5 = 6 90х2 + 50х3 – х6 + у2 = 110 20х2 + 80х3 + х7 = 25 х1 + х2 + х3 + у3= 0,5 х1-7 ³ 0 у1-3 ³ 0 Решим расширенную задачу обычным симплекс-методом. Тогда исходная таблица примет вид таблицы 14.
Таблица 14 – Исходная симплексная таблица для расширенной задачи
Так как задача на минимум, здесь критерий оптимальности нарушен в столбцах при трех первых переменных (в критериальной строке в них стоят положительные коэффициенты). В качестве разрешающего можно выбрать любой из них. Выберем, например, столбец x2. Тогда из базиса выйдет переменная у3. Следующая таблица будет иметь вид таблицы 15.
Таблица 15 – Вторая симплексная таблица для расширенной задачи
Здесь в качестве разрешающего можно выбрать только один элемент: в базис войдет x1, а выйдет у1. Преобразованная таблица примет вид таблицы 16 (результаты расчетов здесь и в дальнейшем приведены с точностью до тысячных долей).
Таблица 16 – Оптимальная симплексная таблица для расширенной задачи
Эта таблица оптимальна, так как положительных коэффициентов в критериальном ограничении нет. Оптимальный план расширенной задачи Так как оптимум положителен, можно сделать вывод, что исходная задача неразрешима, так как ее ОДП пуста. Ответ задачи: составить рацион, удовлетворяющий всем поставленным требованиям, невозможно.
Предположим теперь, что требования к рациону изменились, и теперь предельное содержание белка в нем составляет не 110 г, а всего 44 г. Тогда модель в канонической форме примет вид: min 4х1 + 15х2 + 40х3
380х1 + х2 + 2х3 + х5 = 6 90х2 + 50х3 – х6 = 44 20х2 + 80х3 + х7 = 25 х1 + х2 + х3 = 0,5 х1-7 ³ 0 Решим новую задачу симплекс-методом. Для этого расширенную задачу построим следующим образом: min у1 + у2 + у3
380х1 + х2 + 2х3 + х5 = 6 90х2 + 50х3 – х6 + у2 = 44 20х2 + 80х3 + х7 = 25 х1 + х2 + х3 + у3= 0,5 х1-7 ³ 0 у1-3 ³ 0 Решение расширенной задачи представлено в таблице 17 (слева и сверху указаны номера строк и столбцов электронной таблицы Microsoft Excel).
В результате решения расширенной задачи был получен ее оптимум, равный нулю, и оптимальный план (x1, x2, x3, x4, x5, x6, x7, у1, у2, у3) = (0,009; 0,487; 0,004; 0; 2; 0; 14,93; 0; 0; 0). Следовательно, можно перейти ко второму этапу двухэтапного симплекс-метода, т.е. начать решать исходную задачу, начиная с опорного плана (x1, x2, x3, x4, x5, x6, x7) = (0,009; 0,487; 0,004; 0; 2; 0; 14,93).
Таблица 17 – Решение расширенной задачи
Иными словами, переходят к решению следующей задачи: min 4х1 + 15х2 + 40х3
х4 + х5 = 2 х2 – 0,003х4 – 0,025х6 = 0,487 -0,411х4 - 1,51х6 + х7 = 14,93 х3 + 0,006х4 + 0,025х6 = 0,004 х1-7 ³ 0 Именно такая система уравнений записана в последней симплексной таблице (она представляет собой систему уравнений исходной задачи, подвергнутую линейным преобразованиям). Здесь присутствует полный набор базисных переменных: x1, x5, x2, x7 и х3.
Однако последняя строка таблицы 17, полученная методом Гаусса, соответствует критериальному ограничению расширенной задачи, т.е. другой целевой функции. Чтобы перейти к исходной задаче, это ограничение надо построить заново, т.е. пересчитать его свободный член (значение целевой функции) и коэффициенты по формулам, выведенным в разделе 3.2.2 (в самом деле, ведь базисные переменные опорного плана здесь входят в целевую функцию). Для этого в столбец cб записывают коэффициенты целевой функции исходной задачи при переменных x1, x5, x2, x7 и х3: 4, 0, 15, 0 и 40. Значение целевой функции составит 4*0,009 + 15*0,487 + 40*0,004» 7,5. Первые три коэффициента в критериальном ограничении будут нулевыми, так как переменные x1-3 – базисные, D4 = 4*(-0,003) + 15*(-0,003) + 40*0,006 – 0» 0,2* и так далее.
При использовании для расчетов электронной таблицы рекомендуется вставить перед последней симплексной таблицей (перед строкой 23) еще одну строку, и ввести в нее коэффициенты целевой функции исходной задачи. При этом все последняя таблица сместится на строку вниз и займет диапазон ячеек А24:N30 (см. таблица 18). Новая строка станет строкой № 23, и коэффициентами целевой функции будет заполнен диапазон Е23:К23 (диапазон L23:N23 можно очистить). В столбец (диапазон С25:С29) также надо ввести новые значения коэффициентов целевой функции. Затем изменим критериальное ограничение, которое записано в 30-й строке. Для этого в D30 введем формулу =СУММПРОИЗВ($C25:$C29;D25:D29)-D23, которую затем скопируем по строке на диапазон ячеек Е30:К30. Диапазон L30:N30 также можно очистить (как, впрочем, и диапазон L25:N29, поскольку искусственные переменные в дальнейшем не понадобятся).
Таблица 18 – Переход к решению исходной задачи
Исходная задача здесь также поставлена на минимум. После пересчета критериальной строки становится ясно, что оптимальный план на минимум еще не найден, так как критерий оптимальности нарушается. Положительные коэффициенты 0,179 и 0,629 стоят в обоих небазисных столбцах. Для преобразования таблицы в базис можно ввести либо x4, либо x6. Если провести предварительные расчеты и определить, на сколько уменьшится стоимость рациона в том и другом случае (см. раздел 3.3), станет понятно, что выгоднее ввести в базис x4. Новая таблица примет вид таблицы 19.
Таблица 19 – Оптимальная симплексная таблица
Теперь положительных коэффициентов в критериальной строке нет, т.е. задача на минимум решена. Оптимальный план Х* = (0,011; 0,489; 0; 0,711; 1,289; 0; 15,222), оптимум 7,378. Ответ: для составления рациона следует взять 489 г зерна и 11 г известняка. При этом содержание кальция в рационе будет примерно на 0,7 г выше и на 1,3 г ниже, чем предельно допустимые нормы (от 4 до 6 г). Содержание белка будет на границе нормы, а содержание клетчатки – на 15,2 г меньше максимально допустимого. Стоимость рациона составит 7 руб. 38 коп. в неделю на одного цыпленка. Вопросы и упражнения 1 В чем заключается общая идея методов искусственного базиса? 2 Что можно сказать о разрешимости расширенной задачи? 3 Какова связь между решениями исходной и расширенной задач? 4 В чем сущность двухэтапного симплекс-метода? 5 Решите с помощью Microsoft Excel следующие задачи:
* Обратите внимание, что целевая функция задачи (19) всегда минимизируется, независимо от того, на минимум или на максимум поставлена задача (18). * Не следует путать искусственные переменные с дополнительными, рассмотренными в разделе 1.4.1. Дополнительные переменные не нужно сводить к нулю: в допустимом плане они вполне могут быть положительными, так как вводились в неравенства (левая и правая части неравенства могут отличаться друг от друга на величину дополнительной переменной). * Результат точных расчетов по этим формулам не совпадает, например, со значением D4, приведенным в таблице 17: D4 = 4*(-0,003) + 15*(-0,003) + 40*0,006 – 0 = 0,183 ¹ 0,179. Такое расхождение объясняется погрешностью округлений. Однако правильным для задачи в целом является именно результат 0,179, полученный с помощью электронной таблицы. Не смотря на то, что Microsoft Excel показывает пользователю лишь первые значащие цифры числа, при осуществлении расчетов эта программа оперирует числами со значительно большей точностью. Поэтому проверка расчетов «по последней цифре» в данном случае неприменима. В самом деле, если ввести в две ячейки число 2,4, а в третью – формулу для суммы этих двух ячеек, то сумма составит 4,8. Если при этом потребовать, чтобы числа были показаны с точностью до нуля знаков после запятой, то в первых двух ячейках будет стоять число 2, а в третьей число 5. Казалось бы, результат «2 + 2 = 5» нелеп. Однако на самом деле электронная таблица «помнит» о том, что число 2,4 лишь приближенно равно двум. Поэтому сумма на самом деле приближенно равна 5, а не 4. И в ячейке с суммой на самом деле содержится не число 5, а число 4,8. Дата добавления: 2015-01-18 | Просмотры: 873 | Нарушение авторских прав |
380х1 + х2 + 2х3 – х4 = 4
380х1 + х2 + 2х3 – х4 + у1 = 4
4х1 - 3х2 - х3 + х4 + х5 = 6
х1 + 4х2 + х3 + х5 = 15
2х1 - 4х2 - х3 + х4 = -3
х1-5 ³ 0
4х1 - 3х2 - х3 + х4 + х5 = -10
х1 + 4х2 + х3 + х5 = 15
2х1 - 4х2 - х3 + х4 = -3
х1-5 ³ 0