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

~ ~ Содержание. Задание 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) исходной задачи соответствует переменная двойственной задачи. Таким образом, здесь будут три двойственные переменные . Во-вторых, ограничения двойственной задачи соответствуют столбцам системы (1); неравенства типа превращаются в неравенства типа , а свободными членами становятся коэффициенты при соответствующих переменных целевой

функции (3). В-третьих, целевая функция двойственной задачи оптимизируются не на максимум, а на минимум; коэф¬фициентами становятся свободные члены системы (1). Наконец, двойственные переменные , как и переменные задачи (1)-(3), подчиняются тривиальным условиям неотрицательно¬сти. С учетом этих замечаний задача, двойственная задаче (1)-(3), имеет вид: , (7) (8) (9) Эта задача тоже является задачей линейного программирования и также может быть решена симплекс-методом.

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

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

симплекс-таблицы: . Вектор - вектор первоначальных запасов сырья, - вектор изменения запасов сырья. В данном случае: ; . Сначала определим интервалы устойчивости двойственных оценок по отношению к изменению сырья каждого вида. Запишем неравенство (10): . Матричное неравенство преобразуем в систему скалярных неравенств: или: Рассмотрим устойчивость двойственных оценок к изменению запасов только первого вида сырья, т.е. . Подставляя в систему, найдем: Объединяя эти неравенства, получаем: .

Изменение запасов сырья только второго вида дает нам сле¬дующее: Отсюда получаем: . Аналогично исследуем устойчивость по третьему виду сырья ( : . Как и следовало ожидать, произвольное увеличение недефицитного первого вида сырья не изменит его нулевой двойственной оценки. г) Определение нового оптимального плана при измененных запасах сырья . Проверим выполнение неравенства (10) для условий нашей задачи:

Так как все компоненты полученного вектора неотрицательны, то, при заданных изме¬нениях запаса сырья двойственные оценки не изменятся. Это означает, что второй и третий виды сырья также будут использованы полностью, поэтому второе и третье неравенства системы (1) с измененными правыми частями можно записать как уравнения: Получили систему двух уравнений с двумя неизвестными. Решая её, получаем новый оптимальный план: . Новая стоимость продукции получается подстановкой новых

оптимальных значений в целевую функцию (3): . д) Геометрическое решение исходной задачи. Рассмотрим исходную задачу (1 ) - (3). Поскольку в ней только две переменные , то её можно решить графически на координатной плоскости . Тривиальные неравенства (2) означают, что решение следует искать в первом квадранте системы координат. Нетривиальные неравенства (1) представляют собой полуплоскости, пересечение которых в пределах первого квадранта образует так называемую область допустимых решений (ОДP) задачи

линейного программирования. Оптимальный план представляет собой одну из угловых точек ОДР. Построим, например, полуплоскость, отвечающую первому неравенству системы (1): . Эта полуплоскость лежит с одной стороны от прямой, заданной уравнением: Линию, если она не проходит через начало координат, проще всего построить по двум точкам на осях координат. Строем прямую, получаем две полуплоскости, выше и ниже этой прямой.

Исходному неравенству отвечает только одна из этих полуплоскостей. Она опреде¬ляется подстановкой в неравенство пробной точки, не лежащей на граничной прямой. Например, такой точкой может быть начало координат. Аналогично построив две другие полуплоскости, получим ОДР (рис.1). Теперь надо найти угловую точку ОДР, в которой целевая функция достигает макси¬мума.

Для этого построим вектор роста целевой функции = (50; 70) , который состоит из коэффициентов целевой функции при соответствующих переменных и опорную прямую , перпендикулярную вектору . Передвигая опорную прямую вдоль вектора роста и перпендикулярно ему, получаем, что максимум целевой функции достигается в точке Х – это последняя точка пересечения опорной прямой и ОДР. Точка Х образована пересечением границ 2-го и 3-ro нера¬венств, поэтому эти неравенства запишутся

как уравнения: Из (1): , подставим в (2): Решение этой системы дает оптимальный план первоначальной задачи: Как и следовало ожидать, полученные числа совпадают с решением симплекс-методом. Рис.1. Графическое решение задачи линейного программирования. Задание 2. Транспортная задача. ¬ На трех базах находится однородный груз в количестве т соот¬ветственно. Этот груз необходимо развезти пяти потребителям потребно¬сти которых в данном грузе равны т.

Стоимость перевозок пропорцио¬нальна расстоянию и количеству перевозимого груза. Задана матрица тарифов - стои¬мости перевозки единиц груза от каждой базы каждому потребителю. Необходимо спла¬нировать перевозки так, чтобы их общая стоимость была минимальной. Матрица тарифов: Решение. Составим транспортную таблицу по условиям задачи: ПН ПО Запасы, 16 9 10 12 13 100 5 11 8 6 9 150 7 4 5 16 25 250

Потребности, 100 40 140 60 160 Строки таблицы соответствуют базам (пунктам отправления, ПО), а столбцы - заказчи¬кам (пунктам назначения, ПН). Каждая клетка на пересечении некоторого столбца и какой¬ либо строки соответствует одному маршруту перевозок. Тарифы перевозок указаны в правом верх¬нем углу каждой клетки. Так как сумма запасов равна сумме потребностей: , то говорят, что такая транспортная задача имеет закрытую

модель. Решение транспортной задачи с закрытой моделью поводится по следующему алго¬ритму: Шаг 1. Находится первоначальный опорный план задачи. Шаг 2. Полученный план проверяется на оптимальность (с помощью метода потенциалов). Если план оптимален, то он и будет решением. Иначе переходим к шагу ¬ 3. Шаг 3. Улучшаем план с помощью метода пересчета по циклу и возвращаемся к шагу 2.

На Шаге 1 подготавливается первоначальный опорный план тремя разными методами: методом северо-западного угла, методом минимальной стоимости и методом двойного предпочтения. Затем из этих трех планов выбирается самый выгодный. Его и под¬вергают процедуре дальнейшей оптимизации методом потенциалов. Рассмотрим метод северо-западного угла, или диагональный метод.

В этом методе за¬полнение транспортной таблицы всегда начинается с клетки , т.е. "северо-западного угла" таблицы. Далее, заполнение идет вокруг диагонали таблицы и всегда заканчивается в правом нижнем углу (клетка (3; 5 ). В каждой клетке объем перевозки определяется как наименьшее значение из двух чисел: остатка запаса на базе и остатка заявки потребителя. Отсюда: В результате получаем опорный план : ПН ПО 100 40 140 60 160 100 16 100 9 10 12 13 150 5 11 40 8 110 6 9 250 7 4 5 30 16 60 25 160

В этом опорном плане 6 занятых клеток. В невырожденном плане их должно быть , где т - число баз, п - число заказчиков. Полученный план является выро¬жденным. Подсчитаем общую стоимость перевозок. Она складывается из произведений объемов перевозок и тарифов по всем занятым клеткам: Как видим, при распределении грузов совсем не учитывается стоимость перевозок. Поэто¬му, как правило, метод северо-западного угла дает опорный план, далекий от оптимального.

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

ПН ПО 100 40 140 60 160 100 16 9 10 12 10 13 90 150 5 100 11 8 6 50 9 250 7 4 40 5 140 16 25 70 . Теперь построим опорный план методом двойного предпочтения. При этом сначала в каждом столбце отметим галочкой клетку с наименьшей стоимостью, затем то же самое де¬лаем с каждой строкой. Далее максимально возможные объемы перевозок помещаем в клет¬ки, отмеченные двойной галочкой. Затем распределяем перевозки по клеткам, отмеченным одной галочкой начиная с наименьшей.

В оставшейся части таблицы перевозки распределя¬ем по методу минимальной стоимости. Клетки с двумя галочками: Клетки с одной галочкой: Остальные клетки: Получаем новый опорный план: ПН ПО 100 40 140 60 160 100 16 9 10 12 10 13 90 150 5 100 11 8 6 50 9 250 7 4 40 5 140 16 25 70 . В этом опорном плане 7 занятых клеток. Полученный план является невыро-жденным.

Шаг 2: проверка плана по методу потенциалов. Определяем потенциалы поставщиков и потребителей. На этом этапе составляем систему уравнений для потенциалов, используя только заня¬тые клетки. Используем последний опорный план: Заметим, что в этой системе всего неизвестных, а уравнений всего , поскольку в невырожденном опорном плане всего 7 заполненных клеток. Для однозначного решения не хватает одного уравнения.

В этом случае один из потенциалов, например, приравнивают нулю. Получаем: . Для свободных клеток вычисляем оценки: (11) Среди полученных оценок имеются отрицательные, значит, найденный план неоптимальный. Произведем загрузку клетки (3, 1) с наименьшей оценкой . Строим замкнутый цикл: ПН ПО 100 40 140 60 160 100 16 9 10 «-» 12 10 «+» 13 90 150 «-» 5 100 11 8 «+» 6 50 9 250

«+» 7 4 40 5 140 16 «-» 25 70 Получим новый опорный план: ПН ПО 100 40 140 60 160 100 16 9 10 12 13 100 150 5 90 11 8 6 60 9 250 7 10 4 40 5 140 16 25 60 . Вычисляем оценки свободных клеток: Произведем загрузку клетки (2, 5) . Строим замкнутый цикл: ПН ПО 100 40 140 60 160 100 16 9 10 12 13 100 150 «-» 5 90 11 8 6 60 «+» 9 250 «+» 7 10 4 40 5 140 16 «-» 25 60 Получим новый опорный план:

ПН ПО 100 40 140 60 160 100 16 9 10 12 13 100 150 5 30 11 8 6 60 9 60 250 7 70 4 40 5 140 16 25 . Вычисляем оценки свободных клеток: Так как все оценки неотрицательны, то получен оптимальный план. Запишем решение транспортной задачи: . Задание № 3. Моделирование систем массового обслуживания. Станция автосервиса работает 12 часов в сутки. На станции два здания для рабочих разной специализации.

В первом - боксов для обслуживания отечественных автомоби¬лей, во втором - боксов для ремонта «иномарок». Бригада «отечественного» бокса об¬служивает отечественный автомобиль в среднем за минут, а «иностранная» бригада тратит на иномарку в среднем минут. В течение рабочего дня автомобили прибывают на станцию, в случайные моменты времени с интенсивностью: отечественные - авто¬мобилей в день, иномарки - автомобилей в день. Если хотя бы один из необходимых боксов свободен, то автомобиль сразу же начинает обслуживаться.

Если все заняты, то ав¬томобиль занимает свободное место на стоянке около соответствующего здания. Если за¬няты все места, то он уезжает не обслуженным. Около «отечественного» здания мест, около «иностранного» - . Средняя прибыль, получаемая с отечественных и иностран¬ных автомобилей, одинакова и равна С руб. за машину. Компания рассматривает проект объединенной работы двух зданий, при которой каждый

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

Данные к задаче приведены в следующей таблице: С 2 3 45 60 56 36 4 3 340 70 55 Решение. 1. Сначала определим основные параметры системы до объединения. Находим интенсивность обслуживания автомобилей одним боксом по формуле: . (12) (авт./мин), (авт./мин). Переведем интенсивность из авт./мин в авт./день. С учетом того, что рабочий день на станции 12 часов, а в часу 60 минут, получим: (авт./день), (авт./день).

Вычислим интенсивность нагрузки по формуле: . (13) Определим вероятность того, что все боксы будут свободны по формуле: (14) где: при , при (15) (16) В нашей задаче: . То есть около 1% времени простаивают все «отечественные» боксы и около 4% «иностранные». Вероятность отказа в обслуживании из-за занятости всех боксов и всех мест в очере¬ди определяется по формуле: (17) То есть не обслуживаются из-за полной загруженности 44,2% отечественных автомобилей и 17%

иномарок. Относительная пропускная способность каждого здания равна: (18) Абсолютная пропускная способность - среднее число автомобилей, получив¬ших обслуживание за день, определяется по формуле: (19) Тогда средняя прибыль компании за день равна: (руб.) Среднее время пребывания одного автомобиля на станции (среднее время пребывания в системе) вычисляется по формуле: (20) где - среднее число обслуживаемых автомобилей, - среднее число автомобилей в очереди.

(21) (22) при при (23) В нашей задаче: (раб.день) (мин.). То есть, в «отечественном» здании занято в среднем 1,95 бокса, 2,9 места на стоянке, а отечественный автомобиль проводит на станции в среднем 111,7 минуты (в очереди и во время обслуживания). (раб.день) (мин.). То есть, в «иностранном» здании занято в среднем 2,49 бокса, 0,51 места на стоянке, а иномарка проводит на станции в среднем 72,3 минут.

Для определения среднего времени автомобиля на станции воспользуемся формулой: , где - доли «отечественных» и «импортных» машин в общем потоке. Доля отечествен¬ных автомобилей равна , а доля импортных - . (мин.). То есть «средний» автомобиль проводит на станции 96,3 мин. 2. Теперь определим параметры системы после объединения. Эти параметры будем обозначать волной. Общее число бригад (каналов обслуживания) стало равно:

Общая длина очереди: Вычислим общую интенсивность входящего потока: (авт./день). Определим среднюю интенсивность обслуживания одного «среднего» автомобиля «средней» бригадой. Она может быть вычислена по формуле: , где и - доли «отечественных» и «импортных» бригад в объединенной станции автосервиса; и - средние интенсивности; и - средние времена обслуживания соответ¬ствующими бригадами одной машины объединенного потока. Эти параметры определим по формулам: (авт./мин) = (авт./день) (авт.

/мин)= (авт./день) Доля «отечественных» бригад в общем количестве равна , а доля «импортных» бригад - . Тогда обобщенная интенсивность обслуживания равна: (авт./день). Используя формулы (13) – (22), найдем параметры данной системы. . То есть не обслуживаются из-за полной загруженности «объединенной» станции 30,5% автомобилей. Относительная пропускная способность объединенного автосервиса равна:

Среднее число автомобилей, получивших обслуживание за день, равно: Средняя прибыль компании за день при объединенном автосервисе равна: (руб.) То есть средняя прибыль компании увеличилась. Увеличение прибыли составило около 5 %: Вычислим теперь среднее время пребывания автомобиля на «объединенной» станции. (раб. день) (мин). Таким образом, среднее время пребывания автомобиля на станции заметно увеличилось почти на 16 %: %.

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

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