Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
Краткое сожержание материала:

Размещено на

Содержание

• 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 Решение задачи графическим методом

В первую очередь, найдем область допустимых значений, т.е. точки x₁ и x₂, которые удовлетворяют системе ограничений. По условию задачи x₁ 0, x₂ 0, т.е. мы рассматриваем только те точки, которые принадлежат первой четверти. Рассмотрим неравенство 1 системы ограничений.

3х₁+2х₂3

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

х₁+2/3х₂ 1

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

3х₁+2х₂21, что эквивалентно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3x₁+2x₂?3

x₁+x₂?4

Решив систему уравнений, получим: x₁ = 1, x₂ = 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) Математическая модель задачи

Пусть х₁, х_2, х_3, х_{4 -} число единиц изделий А, Б, В и неокрашенные В. Тогда целевая функция задачи:

W = 25x₁+20x₂+50x₃+30x₄ max.

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

3х₁ + х₂ + 4х₃ + 4х₄ 100

4х₁ + 2х₂ + 5х₃ + 5х₄ 100

5х₁ + 5х₂ + 4х₃ 100

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

х₁0, х₂0, х₃0, х₄0.

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

W_ДВ = 100z₁ +100z₂ +100z₃ min,

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

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

3z₁ +4z₂ +5z₃ 25

z₁ +2z₂ +5z₃ 20

4z₁ +5z₂ +4z₃ 50

4z₁ +5z₂ 30

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

z₁0, z₂0, z₃0.