Симплексный метод решение ЗЛП

Графический способ решения ЗЛП

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит

53. Методы динамического программирования.

Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.

54. Математическая теория игр.

Теория игр представляет собой раздел математики, занимающейся исследованием вопросов поведения и разработкой оптимальных правил (стратегий) поведения каждого из участников в конфликтной ситуации.

Игра представляется как модель любого конфликта, то есть такой ситуации, в которой задействованы несколько участников с различными интересами, мотивами, установками. Для теории игр безразлично кто или что скрывается за игроками: одушевленные или неодушевленные объекты, природа, элемент социального или биологического бытия. Для нее основное то, имеется конфликт и игроки или даже один игрок, которым она предлагает математически точно рассчитанные действия в условиях разной степени неопределенности. Человека же втягивает в игру стремление улучшить свое состояние и позицию в игре и через игру. Неопределенность как магнит притягивает к себе не только игрока, но и наблюдателя, зрителя. «Силой, движущей игроков, является надежда на выигрыш. Привлекательность игр состоит в значительной степени в неопределенности результата. Эта неопределенность побуждает людей вступать в конфликтные ситуации, участвовать в игре не только в качестве игроков, но и в качестве болельщиков». По Ж. Паскалеву получается, сами люди сначала вступают в конфликт, чтобы в условиях неопределенности выиграть, то есть признак выигрыша обязательно присутствует в игре и он является вторичным, производным от самого конфликта. Конфликт должен закончится определенным результатом: чьим-то выигрышем, или проигрышем, или же ничейным результатом.

Итак, в теории игр в качестве базового признака игры принят признак - конфликт. То, что человеческая жизнь есть череда

Однако, даже математическая теория игр не способна стопроцентно предопределить исход некоторых конфликтов. Представляется возможным выделить три основные причины неопределенности исхода игры (конфликта).

Во-первых, это игры, в которых имеется реальная возможность исследования всех или, по крайней мере, большинства вариантов игрового поведения из них одного наиболее истинного, ведущего к выигрышу. Неопределенность вызвана значительным числом вариантов, сложностью их ранжирования по признаку истинности. Человеческий ум в ограниченный отрезок времени просто не в состоянии равным образом исследовать абсолютно все варианты (к примеру, японская игра ГО, русские и международные шашки, британские реверси).

Во-вторых, непрогнозируемое игроками случайное влияние факторов на игру. Эти факторы оказывают решающее воздействие на исход игры и лишь в малой степени могут быть или вообще не могут быть контролируемыми и определяемыми играющими. Окончательный исход игры лишь в малой, крайне незначительной степени определяется самими действиями игроков. «Игры, исход которых оказывается неопределенным в силу случайных причин, называются а з а р т н ы м и (от французского hasard – случай). Исход игры всегда носит лишь вероятностный, предположительный характер (рулетка, игра в кости, игра в «орлянку»).

В-третьих, неопределенность вызвана отсутствием информации о том, какой именно стратегии придерживается играющий против противник. Неведение игроков о поведении соперника носит принципиальный характер и определяется самим правилами игры. Такие игры именуются стратегическими.

Классификация игр строится на основе следующих оснований -признаков:

число участников –одиночные, парные, с тремя участниками, с четверыми участниками и т.д.;

число стратегий – конечные (каждый игрок располагает конечным множеством ходов) и бесконечные (по крайней мере один игрок располагает бесконечным множеством ходов, к примеру игра биологического вида с природой);

характер отношений игроков – бескоалиционные игры, игроки в которых играют каждый за себя и кооперативные игры, игроки объединяются в коалиции с одинаковыми на время игры интересами;

характер выигрыша – игры с нулевой суммой (сумма общего выигрыша не меняется, а лишь перераспределяется или сумма выигрышей всех игроков во всех партиях данной игры нулевая) и игры с ненулевой суммой, к примеру лотерея, в которой организатор всегда выигрывает, а другие игроки (покупатели билетов) всегда получают суммарный выигрыш значительно меньший стоимости билетов;

число ходов – одноходовые и многоходовые, последние из которых разделяются на стохастические, дифференциальные;

состояние информации игры – игры с полной информацией (игроки получают всю игровую информацию после очередного хода соперника) и игры с неполной, или с скрытой информацией.

55. Математическая теория массового обслуживания.

Теория массового обслуживания (теория очередей) — раздел теории вероятностей, целью исследований которого является рациональный выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящие из неё, длительности ожидания и длины очередей ^[1]. В теории массового обслуживания используются методы теории вероятностей и математической статистики.

Теорию потока однородных событий, которая легла в основу теории массового обслуживания, разработал советский математик А. Я. Хинчин.^[2]

Первые задачи ТМО (Теории Массового Обслуживания) были рассмотрены сотрудником Копенгагенской телефонной компании, ученым Агнером Эрлангом, в период между 1908 и 1922 годами. Стояла задача упорядочить работу телефонной станции и заранее рассчитать качество обслуживания потребителей в зависимости от числа используемых устройств.

Имеется телефонный узел (обслуживающий прибор), на котором телефонистки время от времени соединяют отдельные номера телефонов друг с другом. Системы массового обслуживания (СМО) могут быть двух видов: с ожиданием и без ожидания (то есть с потерями). В первом случае вызов (требование, заявка), пришедший на станцию в момент, когда занята нужная линия, остается ждать момента соединения. Во втором случае он «покидает систему» и не требует забот СМО.

Дата добавления: 2015-04-24