Оптимальное одношаговое управление. Транспортная задача
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
ковой вновь преобразуется по тому же алгоритму. Процедура повторяется до тех пор, пока не будет получено оптимальное решение.
таблица 3Свободный членХ11Х12Х22Х33S2000136-5-750-5-505Х13150-1-100000000Х21100-1-1-111/100150110-1Х23150110-1-1/150150110-1Х31200011-1-1/200-150-1-101Х322000-1-10000000
Исходная симплекс-таблица и ее преобразование
Симплекс-таблицей называется таблица упорядоченного расположения записей (11) и (8). В левом верхнем углу клеток записываются коэффициенты целевой функции (верхняя строка) и базисных переменных (следующие строки), выраженных через свободные переменные (табл.3).
Неотрицательные элементы первого столбца таблицы (табл.3, слева) свидетельствуют о том, что исходное базисное решение является допустимым базисным. Наличие в верхней строке таблицы отрицательных элементов свидетельствует о неоптимальности решения. Для перехода к следующей симплекс-таблице выполним такие действия.
Остановим свой выбор на каком-либо из отрицательных элементов первой строки, в данном случае он один, это коэффициент при переменной x33. Переведем ее в базисные переменные. Соответствующий ей столбец симплекс-таблицы обведем двойными линиями. (Этих и последующих построений удобно придерживаться с точки зрения формализации процедуры ручного перехода). На место переменной x33 из базисных переменных нужно перевести ту, которая быстрее всего обращается в нуль, т.е. ту, для которой отношение коэффициента при x33 к соответствующему свободному члену наименьшее (с учетом знака). В правой части таблицы3 приведены эти отношения. Очевидно, наименьшее из них "-1/150". Это значит, что свободная переменная x33 должна поменяться с базисной переменной x23 Обведем соответствующую ей строку таблицы двойными линиями. Элементы этой строки назовем строчными коэффициентами и обведем рамкой.
В клетке на пересечении выделенных строки и столбца запишем обратную величину стоящего в ней коэффициента (внизу справа). В нашем примере ею будет "-1". Назовем ее генеральным столбцовым коэффициентом и возьмем в двойную рамку. Далее заполним выделенный столбец как произведение генерального столбцового коэффициента на соответствующие элементы клеток таблицы. Полученные значения записываем в правых нижних углах соответствующих клеток. Назовем их столбцовыми коэффициентами и обведем рамками. В оставшихся клетках симплекс-таблицы запишем взятое с обратным знаком произведение строчного коэффициента на столбцовый, включая генеральный.
После этого переходим к составлению второй симплекс-таблицы, в которой свободная и базисная переменные поменялись местами.
Составление второй (и последующих) симплекс-таблиц и их анализ
Как и ранее, начнем с заполнения ее левых верхних углов. Строку и столбец, соответствующие новым свободным и базисным переменным, заполним нижними элементами строки и столбца предыдущей таблицы. В остальные клетки запишем суммы значений, стоящие в соответствующих клетках прежней таблицы. Это и будет матричная запись целевой функции и базисных переменных, выраженных через новые свободные переменные (табл.4).
таблица 4Свободный членХ11Х12Х22Х23S1250-4-265-20040-4-4Х13150-1-100-1/150-5010-1-1Х2125000-1-1000000Х33150110-11/15050-1011Х3150-1011-1/5050-1011Х322000-1-10000000
Убедимся, что базисное решение, задаваемое новой таблицей, остается допустимым базисным. Признаком этого служит неотрицательность всех элементов первого столбца составленной симплекс-таблицы. Если какой-либо элемент оказался отрицательным, в выполненные выше расчеты вкралась ошибка. Проверьте их.
Проверяем полученное решение на оптимальность. Признаком оптимальности служит неотрицательность всех элементов первой строки таблицы. В нашем случае коэффициенты отрицателеные. Это означает, что новое допустимое базисное решение также неоптимально. Тем не менее оно лучше предыдущего решения, ибо суммарные затраты на перевозку грузов оказались меньшими (см. первую клетку первой строки). Данному решению отвечает схема транспорта грузов, приведенная на рис.5. Наличие отрицательных элемента первой строки свидетельствует, что возможности улучшения решения не исчерпаны.
Повторим построения и расчеты, проведенные в предыдущем пункте, применительно к данной симплекс-таблице. В результате придем к следующей, третьей симплекс-таблице (табл. 5). Из ее анализа видно, что полученное решение не оптимально и, значит, повторим построения и расчеты, проведенные в предыдущем пункте, применительно к данной симплекс-таблице. Соответствующая схема транспорта груза приведена на рис. 6.
таблица 5Свободный членХ31Х12Х22Х23S10504-221-200-2222Х131001-1-1-1-1/1001001-1-1-1Х2125000-1-1000000Х3320011101/200100-1-1-1-1Х1150-1011000000Х322000-1-10-1/200-100-1111
Повторим построения и расчеты, проведенные в предыдущем пункте, применительно к данной симплекс-таблице. В результате придем к следующей, четвертой симплекс-таблице (табл. 6). Из ее анализа видно, что полученное решение оптимально и, значит, окончательно. Лучшего решения наша задача не имеет. Соответствующая схема транспорта груза приведена на рис. 7.
таблица 6Х31Х13Х22Х23S8502243Х121001-1-1-1Х2125000-1-1Х333000-10-1Х1150-1011В данном случае оптимальное решение получено в результате трех симплекс-переходов. При иных исходных данных или ином выборе свободных и базисных переменных число таких переходов может быть другим.
Решение задачи в условиях аварийной ситуации
Решим ту же зад?/p>