Задача линейного програмирования

~ ~ Содержание.Задание 1. Задача линейного программирования….3 Задание 2. Транспортная задача…15 Задание 3. Моделирование систем массового обслуживания…23 Список использованной литературы ….30 Вариант 3. Задание №1. Задача линейного программирования. Предприятие выпускает два вида продукции А и В, для производства которых ис-пользуется сырье 3 трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида а1, а2, а3 кг соответственно, а для единицы изделия В – b1, b2, b3 кг. Производство обеспеченно сырьем каждого вида в количестве Р1, Р2, Р3 кг соответственно.

Стоимость единицы изделия А составляет руб а единицы изделия В - руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость готовой продукции: а) решите задачу симплекс-методом; б) сформулируйте двойственную задачу и найдите ее решение; в) определите интервалы устойчивости двойственных оценок по отношению к измене-нию сырья каждого вида в отдельности; г) оцените стоимость готовой продукции, если запасы сырья каждого вида на производстве изменились на величину , , кг соответственно; д) решите исходную задачу геометрически. а1 а2 а3 b1 b2 b3 Р1 Р2 Р3 8 10 2 3 9 9 960 1620 1260 -140 -145 -65 50 70 Решение: Составим экономико-математическую модель задачи.

Для этого обозначим - количество изделий вида А, - количество изделий вида В. эта задача является задачей оптимального использования сырья, поэтому система ограничений имеет вид: (1) где справа стоит количество каждого вида сырья, которое не может быть превышено в процессе производства изделий.

Эти ограничения являются нетривиальными. Далее, количество изделий физически является неотрицательными (нельзя произвести отрицательное количество изделий), что дает нам тривиальные ограничения задачи: (2) Наконец, функция цели (целевая функция) представляет собой общую стоимость произведенной продукции, и эта функция в данной задаче оптимизируется на максимум: (3) Для решения задачи симплекс- методом приведем задачу (1) - (3) к каноническому ви-ду; введя дополнительные балансовые переменные, которые означают остатки сырья соответственно l-го, 2-го и 3-го типов.

При этом неравенства (1) преобразуются в уравнения (другими словами, левые части сбалансированы с правыми частями): (4) По смыслу балансовые переменные также неотрицательны, поэтому тривиальная сис¬тема ограничений принимает вид: . (5) Введем балансовые переменные и в целевую функцию с нулевыми коэффициентами: (6) Задача в форме (4)-(6) имеет канонический вид. При этом систему (4) можно записать векторной форме: где , . Здесь векторы, и имеют предпочтительный вид, т.е. являются единичными в одном из компонентов и нулевыми во всех остальных компонентах.

Вектор называется столбцом свободных членов системы ограничений. Для решения задачи (4)-(6) симплекс-методом необходимо иметь опорный план, т.е. допустимое базисное решение системы (4). Для этого все векторы надо разделить на две груп¬пы - базисные и свободные.

Сначала выбираем базисные. Поскольку нетривиальных ограни¬чений всего три, то и базисных векторов будет тоже три. В качестве базисных выбирают век¬торы, имеющие предпочтительный вид, т.е. в данном случае, и. Им соответствуют базисные переменные системы (4). Остальные переменные будут свобод¬ными. При получении базисного решения все свободные переменные приравниваются к нулю. Подставив в (4) , легко получаем остальные компоненты опорного плана: . В векторном виде этот опорный план выглядит так: . Подставив компоненты в (6), получим значение целевой функции для этого плана: . Теперь составим первоначальную симплексную таблицу: СБ Б 0 В верхней строке, над обозначениями векторов, стоят коэффициенты целевой функции при соответствующих переменных.

Нулевое значение над говорит о том, что свободный член в целевой функции отсутствует. Нижняя строка таблицы, которая называется индексной строкой, содержит взятые с обратным знаком значения коэффициентов из верхней строки.

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

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

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

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

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

Для любого элемента первоначальной таблицы можно определить прямоугольник (см. рис.). Здесь - ведущий элемент, - старое значение элемента в искомой ячейке, и - эле¬менты, находящиеся с ними на пересечении строк и столбцов. Новое значение элемента ан получается из формулы: . Получаем таблицу первой итерации симплекс-метода: СБ Б 0 50 70 0 0 0 0 540 22/3 0 1 0 -1/3 0 360 0 0 1 -1 70 140 2/9 1 0 0 1/9 9800 0 0 0 70/9 Произошел переход новому базису: , , . При этом переменные являют¬ся свободными, и в опорном плане их значения равны нулю. Значения остальных перемен¬ных получаем из нового столбца свободных членов: . Запишем опорный план в векторной форме: . Этому плану соответствует значение целевой функции, равное 9800. В новой таблице это значение зафиксировано в индексной строке в столбце свободных членов.

В индексной строке остался один отрицательный элемент, поэтому полученный план не является оптимальным. Значение находится в столбце, поэтому войдет в новый базис.

Минимальное симплексное отношение достигается в строке базисного вектора, который выходит из базиса. Пересчитываем таблицу первой итерации и получаем таблицу второй итерации: СБ Б 0 50 70 0 0 0 0 210 0 0 1 -11/12 7/12 50 45 1 0 0 1/8 -1/8 70 130 0 1 0 -1/36 5/36 11350 0 0 0 155/36 125/36 Аналогично определяем новый опорный план: Ему соответствует значение целевой функции, равное 11350. Поскольку в индексной строке больше нет отрицательных элементов, план является оптимальным: . Итак,

Задача линейного программирования

б) Двойственная задача и её решение. Рассмотрим исходную задачу (1)- (... Изменение запасов сырья только второго вида дает нам сле¬дующее: Отсюд... Поскольку в ней только две переменные, то её можно решить графически н... Иначе переходим к шагу ¬ 3. В каждой клетке объем перевозки определяется как наименьшее значение и...

Моделирование систем массового обслуживания

Около «отечественного» здания мест, около «иностранного» - . Определить целесообразность такого объединения с точки зрения: 1. (раб.день) (мин.). То есть «средний» автомобиль проводит на станции 96,3 мин. 2.

Список использованной литературы

Список использованной литературы . 1. Исследование операций в экономике: Уч. пособие для вузов / Под ред. Н.Ш.Кремера. – М.: Банки и биржи, ЮНИТИ, 2004. – 407 с. 2. Волошин Г.Я. Методы оптимизации в экономике: Уч. пособие. – М.: ДИС, 2004. – 320 с. 3. Фомин Г.П. Системы и модели массового обслуживания в коммерческой деятельности. – М.: Финансы и статистика, 2000. – 144 с.