Графический метод решения задачи линейного программирования
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Содержание
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 системы ограничений.
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), то ее координаты удовлетворяют уравнениям этих прямых:
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) Математическая модель зада