Графический метод решения задачи линейного программирования

После введения добавочных переменных получим систему уравнений: Нужно найти такое допустимое базисное решение системы, которое бы максимизировало целевую функцию F,

Графический метод решения задачи линейного программирования

Контрольная работа

Компьютеры, программирование

Другие контрольные работы по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией

Содержание

 

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 системы ограничений.

 

х1+2х23

 

Преобразуем уравнение следующим образом (разделим на 3):

 

х1+2/3х2 1

 

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой. Рассмотрим неравенство 2 системы ограничений.

 

1+2х221, что эквивалентно

 

Преобразуем уравнение следующим образом (разделим на 21):

 

 

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

Рассмотрим неравенство 3 системы ограничений. х122, что эквивалентно

Преобразуем уравнение следующим образом (разделим на 2):

 

 

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

Рассмотрим неравенство 4 системы ограничений. х12 4, что эквивалентно

Преобразуем уравнение следующим образом (разделим на 4):

 

 

Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой.

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

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Обозначим границы области многоугольника решений.

Построим прямую, отвечающую значению функции F = 3x1+x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области.

 

Рисунок 1.1 - Графический метод решения линейного уравнения

 

Прямая F (x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (4), то ее координаты удовлетворяют уравнениям этих прямых:

 

x1+2x2≤31+x2≥4

 

Решив систему уравнений, получим: x1 = 1, x2 = 3

Откуда найдем минимальное значение целевой функции:

(X) = 3*1 + 1*3 = 6

 

1.3 Проверка решения в MS Excel

 

Ввод данных для решения задачи линейного программирования:

. Создаем форму для ввода условий задачи (рисунок 1.2). Вводим исходные данные.

 

Рисунок 1.2 - Форма ввода условий

 

. Вводим зависимости из математической модели.

 

Рисунок 1.3 - Ввод формул из математической зависимости

 

. Назначение целевой функции. Вызвать меню: Данные, Поиск решения. Заполнить форму поиска решения (рисунок 1.4).

 

Рисунок 1.4 - Поиск решения

 

Рисунок 1.5 - Результат решения задачи

 

Результат решения задачи в MS Excel полностью совпадает с результатом решения графическим методом.

2. Оптимизация плана производства

 

2.1 Условие задачи

 

Мастер Гамбс - владелец небольшого мебельного цеха. Он производит три типа столов: А, Б, и В. Каждая модель стола требует определенных затрат времени на выполнение трех операций: производства заготовок, сбора заготовок и покраски. Мастер имеет возможность продать все столы, которые он производит. Более того, модель В может быть продана и без покраски. Мастер Гамбс нанимает несколько рабочих, которые работают у него по совместительству, так что количество чел-ч, отводимое на каждый вид работ, изменяется от месяца к месяцу.

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

 

МодельЗаготовка, чел-днейСборка, чел-днейПокраска, чел-днейПрибыль, усл. ед. /шт. А Б В Неокрашенные В3 1 4 44 2 5 55 5 4 025 20 50 30

. Какую максимальную прибыль может получить мастер Гамбс (усл. ед.)?

. Следует ли продавать неокрашенные столы типа В?

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

2.2 Решение задачи симплекс-методом

 

1) Математическая модель задачи

Пусть х1, х2, х3, х4 - число единиц изделий А, Б, В и неокрашенные В. Тогда целевая функция задачи:

 

W = 25x1+20x2+50x3+30x4 max.

 

Ограничения по трудовым ресурсам.

 

3х1 + х2 + 4х3 + 4х4 100

х1 + 2х2 + 5х3 + 5х4 100

х1 + 5х2 + 4х3 100

 

Переменные имеют неотрицательные значения:

 

х10, х20, х30, х40.

 

Целевая функция двойственной задачи к исходной:

 

WДВ = 100z1 +100z2 +100z3 min,

 

где Zi, (i = 1,3) - двойственные оценки ресурсов.

Ограничения:

 

z1 +4z2 +5z3 25

z1 +2z2 +5z3 20

z1 +5z2 +4z3 50

z1 +5z2 30

 

Переменные имеют неотрицательные значения:

 

z10, z20, z30.

 

) Решение симплекс методом

Для обращения системы ограничений-неравенств в систему уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные x5, x6, x7. Эти добавочные переменные в условиях данной задачи имеют конкретное экономическое содержание, а именно: объем остатков сырья каждого вида после выполнения плана выпуска продукции.

 

х1 + х2 + 4х3 + 4х4+х5 100

х1 + 2х2 + 5х3 + 5х4 +х6 100

х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Х51003144Х61004255Х71005540F0-25-20-50-30

Разделим каждый элемент ключевой строки (искл

Похожие работы

1 2 >