birmaga.ru
добавить свой файл

1

Тема: Построение математической модели. Симплекс-метод


В3.

Составить математическую модель задачи и решить ее симплекс методом.
Задача:
Для производства двух видов изделий А и В предприятие использует три вида сырья. На производство изделия вида А требуется 12 единиц сырья вида I, 4 единицы сырья вида II и 3 единицы сырья вида III; для производства изделия В необходимо 4 единицы сырья вида I, 4 единицы сырья вида II и 12 единицы сырья вида III. Общее количество сырья на складе: вида I – 300 единиц, сырья вида II – 120 единиц и 252 единицы сырья вида III. Прибыль от реализации изделия А равна 30 рублям, а от реализации изделия В – 40 рублей.

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




2. Составим целевую функцию для данной задачи, где x1 – изделия вида А, x2 – изделия вида В

f = 30x1+40x2 –> max Целевую функцию максимизируем т.к.

по условию задачи требуется найти

максимальную прибыль.
3. Составим систему ограничений, где x1 – изделия вида А, x2 – изделия вида В




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




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








Ответ: Максимальная прибыль 1080;

Производство изделий вида А = 12, и В = 18;

Для производства изделий вида А затрачено материалов вида

I – 144, II – 48, III – 36

Для производства изделий вида В затрачено материалов вида

I – 72, II – 72, III – 216
Алгоритм решения задачи многомерной оптимизации Симплекс-методом.

1. Проверяем, допустимо ли базовое решение (т.е. все ли bi≥0). Если один из свободных членов bi отрицательный, то строка i является «недопустимой» и автоматически становится разрешающей. Ищем в ней отрицательные коэффициенты aij, столбец с отрицательным коэффициентом делаем разрешающим. Если таких коэффициентов нет – значит не существует ОДР, дальше можно не решать.

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

3. Вычисляем оценочные отношения по следующему правилу:





4. Среди ОО выбираем наименьшее и соответствующая строка становится разрешающей.

5. Если все ОО равны бесконечности, это значит, что ОДР незамкнута и функция улучшается в сторону незамкнутости. Оптимальное решение не существует.

ЗАДАНИЕ
(Решить 2-ую задачу так же как и первую, т.е. 1ая задача это пример(образец))

Составить математическую модель задачи и решить ее симплекс методом.

Задача 2. Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно. Стоимость перевозок от первого поставщика всем потребителям составляет $7, $6 и $4 соответственно, от второго поставщика – $3, $8 и $5, а от третьего – $2, $3 и $7. Необходимо определить наиболее дешевый вариант перевозок, при этом каждый поставщик должен отправить столько груза, сколько имеется у него в запасе, а каждый потребитель должен получить нужное ему количество продукции.
И еще... нужны объяснения к 1-ой задачи
Расписать подробнее на словах как мы получаем эту/эти таблицы и что обозначают выделенные цифры, почему именно их выделяем (сиреневым и оранжевым)?
5. Решаем задачу Симплекс-методом используя алгоритм приведенный ниже