Графический метод решения задачи линейного программирования
Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 02.05.2012 |
| Размер файла | 2,0 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
- 1. Графический метод решения задачи линейного программирования
- 1.1 Условие задачи
- 1.2 Решение задачи графическим методом
- 1.3 Проверка решения в MS Excel
- 2. Оптимизация плана производства
- 2.1 Условие задачи
- 2.2 Решение задачи симплекс-методом
- 2.3 Решения задачи в MS Excel
- 3. Многоканальная система массового обслуживания
- 3.1 Теоретические сведения
- 3.2 Постановка задачи
- 3.3 Решение задачи
- Список использованной литературы
1. Графический метод решения задачи линейного программирования
1.1 Условие задачи
Решить графически задачу линейного программирования. Проверить решение в Excel.
1.2 Решение задачи графическим методом
В первую очередь, найдем область допустимых значений, т.е. точки x1 и x2, которые удовлетворяют системе ограничений. По условию задачи x1 0, x2 0, т.е. мы рассматриваем только те точки, которые принадлежат первой четверти. Рассмотрим неравенство 1 системы ограничений.
3х1+2х23
Преобразуем уравнение следующим образом (разделим на 3):
х1+2/3х2 1
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой. Рассмотрим неравенство 2 системы ограничений.
3х1+2х221, что эквивалентно
Преобразуем уравнение следующим образом (разделим на 21):
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.
Рассмотрим неравенство 3 системы ограничений. х1-х22, что эквивалентно
Преобразуем уравнение следующим образом (разделим на 2):
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.
Рассмотрим неравенство 4 системы ограничений. х1+х2 4, что эквивалентно
Преобразуем уравнение следующим образом (разделим на 4):
Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой.
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Построим прямую, отвечающую значению функции F = 3x1+x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области.
Рисунок 1.1 - Графический метод решения линейного уравнения
Прямая F (x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (4), то ее координаты удовлетворяют уравнениям этих прямых:
3x1+2x2?3
x1+x2?4
Решив систему уравнений, получим: x1 = 1, x2 = 3
Откуда найдем минимальное значение целевой функции:
F (X) = 3*1 + 1*3 = 6
1.3 Проверка решения в MS Excel
Ввод данных для решения задачи линейного программирования:
1. Создаем форму для ввода условий задачи (рисунок 1.2). Вводим исходные данные.
Рисунок 1.2 - Форма ввода условий
2. Вводим зависимости из математической модели.
Рисунок 1.3 - Ввод формул из математической зависимости
3. Назначение целевой функции. Вызвать меню: Данные, Поиск решения. Заполнить форму поиска решения (рисунок 1.4).
Рисунок 1.4 - Поиск решения
Рисунок 1.5 - Результат решения задачи
Результат решения задачи в MS Excel полностью совпадает с результатом решения графическим методом.
2. Оптимизация плана производства
2.1 Условие задачи
Мастер Гамбс - владелец небольшого мебельного цеха. Он производит три типа столов: А, Б, и В. Каждая модель стола требует определенных затрат времени на выполнение трех операций: производства заготовок, сбора заготовок и покраски. Мастер имеет возможность продать все столы, которые он производит. Более того, модель В может быть продана и без покраски. Мастер Гамбс нанимает несколько рабочих, которые работают у него по совместительству, так что количество чел-ч, отводимое на каждый вид работ, изменяется от месяца к месяцу.
Используйте данные таблицы и постройте модель линейного программирования, которая помогла бы мастеру найти такую программу выпуска продукции, которая максимизировала бы его прибыль в следующем месяце. Предполагается, что по каждому виду работ возможны трудозатраты до 100 чел-ч.
|
Модель |
Заготовка, чел-дней |
Сборка, чел-дней |
Покраска, чел-дней |
Прибыль, усл. ед. /шт. |
|
|
А Б В Неокрашенные В |
3 1 4 4 |
4 2 5 5 |
5 5 4 0 |
25 20 50 30 |
1. Какую максимальную прибыль может получить мастер Гамбс (усл. ед.)?
2. Следует ли продавать неокрашенные столы типа В?
3. На сколько увеличится прибыль, если объем использования трудовых ресурсов на каждой работе возрастет на 1%? (Для ответа на этот вопрос не требуется проведения оптимизационных расчетов.)
2.2 Решение задачи симплекс-методом
1) Математическая модель задачи
Пусть х1, х2, х3, х4 - число единиц изделий А, Б, В и неокрашенные В. Тогда целевая функция задачи:
W = 25x1+20x2+50x3+30x4 max.
Ограничения по трудовым ресурсам.
3х1 + х2 + 4х3 + 4х4 100
4х1 + 2х2 + 5х3 + 5х4 100
5х1 + 5х2 + 4х3 100
Переменные имеют неотрицательные значения:
х10, х20, х30, х40.
Целевая функция двойственной задачи к исходной:
WДВ = 100z1 +100z2 +100z3 min,
где Zi, (i = 1,3) - двойственные оценки ресурсов.
Ограничения:
3z1 +4z2 +5z3 25
z1 +2z2 +5z3 20
4z1 +5z2 +4z3 50
4z1 +5z2 30
Переменные имеют неотрицательные значения:
z10, z20, z30.
2) Решение симплекс методом
Для обращения системы ограничений-неравенств в систему уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные x5, x6, x7. Эти добавочные переменные в условиях данной задачи имеют конкретное экономическое содержание, а именно: объем остатков сырья каждого вида после выполнения плана выпуска продукции.
3х1 + х2 + 4х3 + 4х4+х5 100
4х1 + 2х2 + 5х3 + 5х4 +х6 100
5х1 + 5х2 + 4х3+х7 100
хi0, (i=1,2.7).
После введения добавочных переменных получим систему уравнений: Нужно найти такое допустимое базисное решение системы, которое бы максимизировало целевую функцию F, т.е. необходимо найти оптимальное решение задачи. Так как система ограничений состоит из трех независимых уравнений с семью переменными, то число основных (базисных) переменных должно равняться трем, а число неосновных - четырем. Для решения задачи симплексным методом, прежде всего, нужно найти любое базисное решение. В условиях данной задачи оно может быть найдено без труда. Для этого достаточно принять за основные добавочные переменные x5, x6, x7. Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель (определитель единичной матрицы равен 1, т.е. отличен от нуля). Основные переменные x5, x6, x7. Составляем первую симплекс-таблицу. Находим разрешающий элемент.
- просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов ) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
- просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке - ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
- среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка, в которой он находится ключевой;
|
Базисные переменные |
Своб. члены |
Х1 |
Х2 |
Х3 |
Х4 |
|
|
Х5 |
100 |
3 |
1 |
4 |
4 |
|
|
Х6 |
100 |
4 |
2 |
5 |
5 |
|
|
Х7 |
100 |
5 |
5 |
4 |
0 |
|
|
F |
0 |
-25 |
-20 |
-50 |
-30 |
Разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
- в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.
- столбец, у которого в ключевой строке имеется 0, в новой таблице будет таким же.
- строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.
|
Базисные переменные |
Своб. члены |
Х1 |
Х6 |
Х3 |
Х4 |
|
|
Х5 |
20 |
-1/5 |
-3/5 |
0 |
0 |
|
|
Х3 |
20 |
4/5 |
2/5 |
1 |
1 |
|
|
Х7 |
20 |
1 |
17/5 |
0 |
-4 |
|
|
F |
1000 |
15 |
0 |
0 |
20 |
Так как в строке F нет отрицательных элементов, то найдено оптимальное решение F=1000, при значениях переменных равных: X3=20.
2.3 Решения задачи в MS Excel
Так как переменные задачи входят в целевую функцию и ограничения задачи линейно, то соответствующая задача оптимизации является задачей линейного программирования и для её эффективного решения можно применить приложение MS Excel.
1. Создаем форму для ввода условий задачи (рисунок 2.1). Вводим исходные данные и зависимости из математической модели.
Рисунок 2.1 - Форма ввода данных
2. Назначение целевой функции. Вызвать меню: Данные, Поиск решения. Заполнить форму поиска решения (рисунок 2.2).
Рисунок 2.2 - Поиск решения
3. Результат поиска решения.
Рисунок 2.3 - Результат поиска решения задачи
Анализ задачи:
Внутренняя структура решения задачи в Excel может быть проанализирована с помощью 3-х отчетов:
1. Отчет по результатам.
2. Отчет по устойчивости.
3. Отчет по пределам.
Рисунок 2.4 - Отчет по результатам
Из отчета по результатам видно, что для получения максимальной прибыли в размере 1000 усл. ед. необходимо производить 20 единиц изделия В.
2 ресурс расходуется полностью, т.е. является дефицитным.
Рисунок 2.5 - Отчет по устойчивости
Теневая цена - это удельная прибыль, т.е. размер дополнительной прибыли, которую можно получить, увеличив запас ресурса на один. Так как запас ресурса равен 100, а увеличение его на один процент равен 101, т.е. на один, то можно считать, что при увеличении трудовых ресурсов на 1% произойдет увеличение прибыли на 10 усл. ед. (значение теневой цены).
Рисунок 2.6 - Отчет по пределам
Из отчета по пределам видно, что производство изделий типа В обеспечивает максимальную прибыль.
2.4 Ответы на поставленные вопросы
1. Прибыль предпринимателя принимает максимальное значение 1000 усл. ед. при реализации 20 единиц продукции В.
2. Неокрашенные изделия типа В по оптимальному плану продавать не следует, х4=0. В оптимальный план производства могут попасть только рентабельные, неубыточные виды продукции.
3. При увеличении использования трудовых ресурсов на каждой работе на 1% максимальная прибыль увеличивается на 10 усл. ед., т.е. на 1%.
3. Многоканальная система массового обслуживания
3.1 Теоретические сведения
Средства, обслуживающие требования, называются обслуживающими устройствами или каналами обслуживания. Например, к ним относятся каналы телефонной связи, посадочные полосы, мастера-ремонтники, билетные кассиры, погрузочно-разгрузочные точки на базах и складах.
Совокупность однотипных обслуживающих устройств называется система массового обслуживания (СМО). Такими системами могут быть телефонные станции, аэродромы, билетные кассы, ремонтные мастерские, склады и базы снабженческо-сбытовых организаций и т.д.
По составу СМО бывают одноканальные (с одним обслуживающим устройством) и многоканальными (с большим числом обслуживающих устройств). Многоканальные системы могут состоять из обслуживающих устройств как одинаковой, так и разной производительности.
Основными элементами СМО являются: входящий поток требований, очередь требований, обслуживающие устройства, (каналы) и выходящий поток требований. Изучение СМО начинается с анализа входящего потока требований. Входящий поток требований представляет собой совокупность требований, которые поступают в систему и нуждаются в обслуживании. Входящий поток требований изучается с целью установления закономерностей этого потока и дальнейшего улучшения качества обслуживания. Среднее число требований, поступающих в систему обслуживания за единицу времени, называется интенсивностью поступления требований и определяется следующим соотношением:
где Т - среднее значение интервала между поступлением очередных требований.
В подавляющем большинстве случаев на практике система массового обслуживания является многоканальными, то есть параллельно могут обслуживаться несколько заявок, и, следовательно, модели с обслуживающими каналами (где число каналов обслуживания n>1) представляют несомненный интерес.
Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока л, при этом параллельно может обслуживаться не более n клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняется 1/м. Режим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, при чем длительность процедуры обслуживания каждым из каналов является случайной величиной, починенной экспоненциальному закону распределения. Конечная цель использования параллельно включенных обслуживающих каналов заключается в повышение (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно n клиентов.
Стационарное решение системы имеет вид:
где, .
Формулы для вычисления вероятностей называются формулами Эрланга.
Определим вероятностные характеристики функционирования многоканальной СМО с отказами в стационарном режиме:
вероятность отказа:
так как заявка получает отказ, если приходит в момент, когда все каналов заняты. Величина Ротк характеризует полноту обслуживания входящего потока;
вероятность того, что заявка будет принята к обслуживанию (она же - относительная пропускная способность системы) дополняет Ротк до единицы:
Абсолютная пропускная способность
среднее число каналов, занятых обслуживанием () следующее:
Величина характеризует степень загрузки СМО.
линейное программирование графический метод
3.2 Постановка задачи
Пусть n-канальная СМО представляет собой вычислительный центр (ВЦ) с тремя (n=3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступающих на ВЦ, имеет интенсивность л=1 задача в час. Средняя продолжительность обслуживания tоб=1,8 час.
Требуется вычислить значения:
вероятности числа занятых каналов ВЦ;
вероятности отказа в обслуживании заявки;
относительной пропускной способности ВЦ;
абсолютной пропускной способности ВЦ;
среднего числа занятых ПЭВМ на ВЦ.
Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.
3.3 Решение задачи
Определим параметр м потока обслуживаний:
Приведенная интенсивность потока заявок
Предельные вероятности состояний найдем по формулам Эрланга:
Вероятность отказа в обслуживании заявки
относительная пропускная способность ВЦ
Абсолютная пропускная способность ВЦ:
Среднее число занятых каналов - ПЭВМ
Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех - остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (Р3= 0,180). Очевидно, что пропускную способность ВЦ при данных л и м можно увеличить только за счет увеличения числа ПЭВМ.
Определим, сколько нужно использовать ПЭВМ, чтобы сократить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу вероятности отказа:
Составим следующую таблицу:
|
n |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
P0 |
0,357 |
0,226 |
0,186 |
0,172 |
0,167 |
0,166 |
|
|
Pотк |
0,673 |
0,367 |
0,18 |
0,075 |
0,026 |
0,0078 |
Анализируя данные таблицы, следует отметить, что расширение числа каналов ВЦ при данных значениях л и м до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение задач на 99,22%, так как при n = 6 вероятность отказа в обслуживании (Ротк) составляет 0,0078.
Список использованной литературы
1. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.
2. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. М.: Изд-во МГУ, 1984.
3. Советов Б.А., Яковлев С.А. Моделирование систем, М: Высшая школа, 1985.
Размещено на Allbest.ru
Подобные документы
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014
