47511 (Линейное программирование), страница 4

3. Практическая часть

Постановка задачи: Для производства трёх видов продукции используется три вида сырья. Нормы затрат каждого из видов сырья на единицу продукции данного вида, запасы сырья, а также прибыль с единицы продукции приведены в таблице:

Определить план выпуска продукции для получения максимальной прибыли, чтобы сырьё IIвида было израсходовано полностью. Оценить каждый из видов сырья, используемых для производства продукции.

Вид таблицы по заданию поставленной задачи:

Решение поставленной задачи:

Предположим, что производится x₁ изделий А, изделий В и изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции

3.1.Построим математическую модель задачи:

тогда функция цели:

Z-0 = 3X₁ + 7X₂ + 2X₃ – совокупная прибыль от продажи произведенной продукции, которую требуется максимизировать.

Подсчитаем затраты сырья:

Сырье 1-го типа: 4 х1 + 2 х2 + 0 х3 , по условию затраты не превосходят 19,

Сырье 2-го типа: 0 х1 + 1 х2 + 1 х3, по условию затраты не превосходят 8,

Сырье 3-го типа: 1x1 + 2x2 + 0x3, по условию затраты не превосходят 24.

при следующих условиях:

X₁, X₂, X₃ ≥ 0.

4X₁+2X₂+X₄ ≤ 19

X₂ + X₃ +X₅ = 8

X₁+ 2X₂+X₆ ≤24

3.2 Выбираем метод решения и приводим задачу к каноническому виду:

Пришли к задаче линейного программирования:

припишем каждому из видов сырья, используемых для производства продукции. Тогда общая оценка сырья, используемого на производство продукции, составит:

Получили математическую модель. Необходимо максимизировать функцию цели ↓

Z-0 (x1, x2, x3) = 3X₁ + 7X₂ + 2X₃ → max

Введем дополнительные переменные X₄, X₅, X₆.

Преобразуем первое ограничение:

Получили задачу:

4X₁+2X₂+X₄ = 19

X₂ + X₃ +X₅ = 8

X₁+2X₂ +X₆ =24

3.3 Решаем задачу путем сведения к задаче линейного программирования:

X_i≥0 ; 0-Z= -3X_1- -7X_2- -2X₃

Приведем задачу к канонической форме.

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

Требуется найти вектор , доставляющий максимум линейной форме

при условиях

где

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

Строим начальную симплекс-таблицу:

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке 0-Z есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке 0-Z (-7). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Пересчитаем таблицу:

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке 0-Z есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке 0-Z (-3). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Тогда каноническую форму задачи ЛП можно представить в следующем матричном виде эквивалентном первоначальному:

Z=CX →max,

AX=B,

X≥0.

где 0 - нулевая матрица-столбец той же размерности, что и матрица X.

замечание.

Не ограничивая общности, можно полагать, что свободные члены неотрицательны, т.е. b i ≥ 0, где i =¯1,m (иначе ограничительные уравнения можно умножить на (-1)).

Пересчитаем таблицу:

Эта таблица является последней, по ней читаем ответ задачи.

Найдено оптимальное базисное решение:

При котором Z max = 233/4= 58,25 ден. ед.

План производства:

X₁ =3/4= 0,75; X₂ = 0; X₃ = 0; X₄ = 3; X₅ = 0; X₆ = 29/4= 7,25