Математическое программирование 02

Задание 2. Составить экономико-математическую модель задачи об использовании сырья и решить ее графически.

Решение: Математическая модель задачи имеет вид:

Решим задачу графическим методом. Построим по полученной системе ограничений многоугольник допустимых решений и найдем оптимальный план производства геометрическим путем.

Для этого в системе координат построим прямые , и . Как известно, прямую можно построить по двум точкам. Задавая переменной X1 произвольные значения, вычислим по указанным уравнениям соответствующие значения X2.

Выделим полуплоскости, соответствующие условиям ограничений. Например, для прямой возьмем точку (0,0) и подставим ее в неравенство , получим верное неравенство 0 ≤ 35. Следовательно, нужно выбрать полуплоскость, Включающую начало координат. Аналогичным образом выбираются остальные полуплоскости. Получим чертеж (см. рис. 1). Областью допустимых значений переменных x1 и x2 является внутренняя область пятиугольника OАВСD. Основное свойство решения задачи линейного программирования – выпуклость многоугольника планов – выполнено.

Перемещая линию уровня вдоль направления вектора , получим, что функция имеет максимум в точке B(5, 6)

Итак X1 = 5 и X2 = 6.

При этом max F = 2×5 + 3×6 = 28.

Задание 3. Решить задачу о назначениях по данной матрице стоимостей.

Решение: Предположим, числа в приведенной таблице имеют смысл производительности труда I-го работника, назначенного на J-ю работу, тогда математическая модель задачи имеет вид:

Xij = 1, если I-й работник будет назначен на J-ю работу; Xij = 0 – в противном случае.

Поскольку каждый работник будет назначен только на одну работу, то

Так как каждая работа выполняется только одним работником, то

Суммарная выработка выражается функцией , где Cij - выработка на J-Й работе при её выполнении I-М работником.

Результатом решения данной задачи является так называемая матрица назначений, в которой в каждой строке все элементы, кроме одного, равны нулю и в каждом столбце которой все элементы, кроме одного, равны нулю. Тот факт, что элемент Cij = 1 означает, что I-й рабочий будет выполнять J-ю работу.

Решим задачу венгерским методом. Поскольку в задаче нужно найти максимум целевой функции, изменим знак каждого значения таблицы на противоположный и прибавим к нему число 21 – максимальное из чисел таблицы. Получим:

Этап 1. В каждой строке ищем минимальный элемент (выделяем жирным в таблице) и отнимаем от всех элементов строки.

Теперь проводим аналогичную процедуру для всех столбцов: ищем наименьший элемент по столбцу и отнимаем его из всех элементов столбца.

Получим:

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

Этап 2. Выбираем строки с одним нулем, выделяем нуль жирным и зачеркиваем оставшиеся нулевые значения данного столбца.

Получаем оптимальную матрицу назначений:

Максимальное значение целевой функции: 12 + 17 + 18 + 21 = 68.

Задание 4. Решить задачу линейного программирования симплексным методом.

Решение: Запишем модель задачи в каноническом виде, введя дополнительные переменные.

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

По наибольшему по модулю отрицательному значению Z-строки выберем разрешающий столбец. Это столбец X2. Вычислим с его элементами симплексные отношения, разделив значения столбца свободных членов на соответствующие элементы этого столбца. По наименьшему симплексному отношению выберем разрешающую строку. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент. Проведем с ним симплексное преобразование по следующим правилам:

1.  Элементы разрешающего столбца, за исключением разрешающего элемента, заменяются нулями, разрешающий элемент заменяется единицей;

2.  Элементы разрешающей строки делятся на разрешающий элемент;

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

При этом переменная, стоящая в разрешающем столбце, включается в базис, а переменная, стоящая в разрешающей строке, исключается из базиса.

Результаты симплексных преобразований приведены в таблице.

Запишем компоненты полученного плана:

X1 = 4; X2 = 8; X3 = 0; X4 = 0; X5 = 3.

При этом значение функции F будет равно 32.

© 2011-2024 Контрольные работы по математике и другим предметам!