Линейное программирование, решение задач симплексным методом

Введение

Линейное программирование как раздел исследования операций имеет почти сорокалетнюю историю. Внедрение вычислительной техники дало значительный толчок исследованиям в этой области математики. Был разработан ряд алгоритмов решения задач линейного программи­рования, а в последующие годы были созданы программы и пакеты программ преимущественно для больших ЭВМ. Основная масса лите­ратуры по. линейному программированию в нашей стране выпущена в 60 - 70-е годы. Исследования в этой области (как теоретические, так и прикладные) продолжаются и в настоящее время.

Методы линейного программирования оказались весьма эффектив­ными для решения некоторых задач из области исследования операций. Слово "программирование" мы понимаем как планирование, и это определяет характер рассматриваемых приложений. Основные идеи линейного программирования возникли во время второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и управлении — как в местных, так и в государственных мас­штабах. Этими методами можно решить многие (хотя не все) задачи, связанные с эффективным использованием ограниченных ресурсов.

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

Исследование операций — научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами.

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

Целью всякого моделирования является исследование объек­та вначале на качественном, а затем по мере накопления ин­формации и развития модели на все более точных количествен­ных уровнях.

Данные соображения могут быть проиллюстрированы про­стым примером. Существовал (и существует) метод «теория ве­роятностей» как широкий класс математических моделей, опе­рирующих понятиями «вероятность», «случайное событие», «случайная величина», «математические ожидание (среднее зна­чение) случайной величины», «дисперсия (рассеяние)» и т. д. На границе XIX и XX вв. появляется новый объект - коммутируе­мая система телефонной связи, с которой ассоциируются поня­тия «заявка на соединение», «отказ», «время ожидания соедине­ния», «коммутация» и другие характеристики системы.

В 20-е гг. А. К. Эрланг соединил эти метод и объект; в резуль­тате была создана математическая теоретико-вероятностная мо­дель процессов в коммутируемых телефонных сетях, оперирующая понятиями «поток заявок», «среднее время ожидания», «средняя длина очереди на обслуживание», «дисперсия времени ожидания», «вероятность отказа» и т. д. Дальнейшее развитие это­го научного направления показало плодотворность понятийной базы данной модели, ее широкие конструктивные возможности. Модель развилась в метод исследования сложных систем — «тео­рию массового обслуживания», терминология и понятийная база которого абстрагировались от ассоциаций с телефонными сетями и обрели общетеоретический характер. И теперь новые модели могут строиться путем применения теории массового обслужива­ния к другим объектам (производственные процессы, операцион­ные системы ЭВМ, транспортные потоки и пр.).

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

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

Главный метод исследования операций — системный анализ целенаправленных действий (операций) и объективная (в част­ности, количественная) сравнительная оценка возможных результатов этих действий.

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