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

Введение

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

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

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

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

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

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

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

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

другим объектам (производственные процессы, операционные системы ЭВМ, транспортные потоки и пр.).

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

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

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

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

Считается, что исследование операций зародилось накануне второй мировой войны, когда в Англии на одной радиолокационной станции была создана группа специалистов для решения технических задач с помощью математики. Они сосредоточили внимание на сравнении эффективности путей решения задач, поиске оптимального решения. Участие в этой группе представителей разных специальностей предопределило комплексный, или, как теперь принято говорить, системный, подход. В настоящее время в этом направлении работают сотни исследовательских учреждений и групп в десятках стран. Организованы общества исследования операций, объединяемые международной федерацией (ИФОРС).

В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л.В.Канторович, Н.П. Бусленко, Е.С. Вентцель, Н.Н. Воробьев, Н.Н. Моисеев,Д.Б. Юдин и многие другие.

Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черчмен, А. Кофман и др.

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

Т. А. Саати: «Исследование операций представляет собой искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими способами».

ЦЕНТРАЛЬНЫЙ МЕЖРЕГИОНАЛЬНЫЙ ТЕХНИКУМ ОТРАСЛЕВЫХ ТЕХНОЛОГИЙ И ПРЕДПРИНИМАТЕЛЬСТВА

Утверждаю

Зам. директора по учебной части

« » 200 г.

ЗАДАНИЕ

на курсовое проектирование

по предмету «Математические методы»

Студенту: Сергееву Евгению Анатольевичу.

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

1. Введение
2. Теоретическая часть
3. Практическая часть

Задачи и их решение:

Задача первая:

Решить задачу симплекс методом:

X₁+3X₂≤300

X₁+X₂≤150

X₁≥0

X₂≥0

F = 2X₁+3X₂ → max

3.1.2 Задача вторая:

Предприятие выпускает продукцию двух видов. Виды сырья, его запасы, нормы расхода сырья на у. е. каждого вида продукции, прибыль производства от реализации продукции даны в таблице:

Виды сырья	Расход сырья на продукцию		Запасы сырья
	1	2
1	1	3	20
2	2	1	10
3	2	2	17
Прибыль	2	1

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?