Оптимизация доставки грузов и план выпуска продукции

В нашем примере это получение максимальной прибыли от реализации произведенной продукции. Если обозначить функцию размера прибыли через Z, тоосновная цель предприятия может быть выражена так: Максимизировать целевую функцию Z = 60×1 + 50×2+ 40×3+ 32×4Перепишем это условие в следующей форме:

60×1 + 50×2+ 40×3+ 32х4max. Таким образом, математическая модель оптимизации выпуска продукции может быть записана в следующем виде:

Найти неизвестные значения переменных х1, х2,х3,х4, удовлетворяющие ограничениям5×1 + 4×2+ 2×3+ 5×4<= 7044×1 + 28×2+ 36×3+ 60×4<= 80 011×1 + 15×2+ 8×3+ 17×4<= 400×1 0, х2 0, х3 0, х40и доставляющих максимальное значение целевой функцииZ = 60×1 + 50×2+ 40×3+ 32х4max. Построенная модель является задачей линейного программирования. Любое решение, удовлетворяющее ограничениям модели, называется допустимым, а допустимое решение, доставляющее максимальное значение целевой функции, называется оптимальным.

3.2. Решение задачи оптимизации плана выпуска продукции симплекс-методом

Вычислим оптимум функции симплекс-методом.Введем добавочные неотрицательные переменные х5, х6, х7 и приведем систему неравенств к системе уравнений (к каноническому виду):Проще всего получить базисное решение системы уравнений, если за основные переменные взять добавочные переменные х5, х6, х7 (минор из коэффициентов при х5, х6, х7 отличен от 0).Шаг1. Основные переменные (ОП) — х5, х6, х7;Неосновные переменные (НП) — х1, х2, х3, х4Выразим ОП через НП, получим систему уравнений:

Линейная форма Z = 60×1 + 50×2 + 40×3 + 32×4, или Z — 60×1- 50×2- 40×3- 32×4= 0уже выражена через эти же свободные члены. Заполним симплекс-таблицу:

Таблица 1Базисные переменные

Свободные членых1×2×3×4×5×6×7×5 705 425 100×680 044 283 660 010×7 400 111 581 7001Z0−60−50−40−32 000 В последней строке имеем 4 отрицательные оценки. Выберем наименьшую — это -60 и просматриваем столбец для х1: имеем числа 5, 44, 11. Делим на эти числа соответствующие свободные члены: 70/5, 800/44, 400/11. Из полученных частных наименьшее есть 70/5. Следовательно, разрешающим является элемент 1. Выделим соответствующие строку и столбец. Новый базис состоит из х1, х6, х7. Для составления следующей таблицы умножим выделенную строку таблицы 1 на 1/5, чтобы получить на месте разрешающего элемента 1. И полученную строку пишем на место прежней в таблицу 2. К каждой из остальных строк прибавляем вновь полученную, умноженное на такое число, чтобы в клетках разрешающего столбца появлялись нули. Таблица 2Базисные переменные

Свободные членых1×2×3×4×5×6×7×11 414/52/511/500×61 840−36/592/516−44/510×7 246 031/518/56−11/501Z8400−2-16 281 200

Далее ищем разрешающие столбец и строку в таблице 2. В последней строке две отрицательные оценки, наименьшая из них -16, просматриваем столбец для х3: имеем числа 2/5, 92/5, 18/5. Делим на эти числа соответствующие свободные члены. Из полученных частных наименьшее есть 184 * 5 / 92. Следовательно, разрешающим является элемент 6. Выделим соответствующие строку и столбец. Новый базис состоит из х1, х3, х7. Для составления следующей таблицы умножим выделенную строку таблицы 2 на 5/92, чтобы получить на месте разрешающего элемента 1. И полученную строку пишем на место прежней в таблицу 3. К каждой из остальных строк прибавляем вновь полученную, умноженное на такое число, чтобы в клетках разрешающего столбца появлялись нули. Таблица 3Базисные переменные

Свободные членых1×2×3×4×5×6×7×110 122/23015/239/23−1/460×3100−9/23 120/23−11/235/920×72 100 175/23066/23−11/23−9/461Z10000−190/230 964/23100/2320/230Ищем разрешающие столбец и строку в таблице 3. В последней осталась последняя отрицательная оценка, просматриваем столбец для х2: имеем положительные числа 22/23, 175/23. Делим на эти числа соответствующие свободные члены. Из полученных частных наименьшее есть 230 / 22. Следовательно, разрешающим является элемент 1. Выделим соответствующие строку и столбец. Новый базис состоит из х2, х3, х7. Для составления следующей таблицы умножим выделенную строку таблицы 3 на 23/22, чтобы получить на месте разрешающего элемента 1. И полученную строку пишем на место прежней в таблицу 4. К каждой из остальных строк прибавляем вновь полученную, умноженное на такое число, чтобы в клетках разрешающего столбца появлялись нули. Таблица 4Базисные переменные

Свободные членых1×2×3×4×5×6×7×2115/1123/221 015/229/22−1/440×3155/119/220 125/22−7/221/220×71 435/11−175/2200−51/22−79/22−1/441Z11950/1195/1 100 523/1185/1115/220Т.к. все коэффициенты при переменных положительны, то дальнейшее увеличение целевой функции невозможно. Значит, полученное оптимальное базисное решение является и оптимальным. Получен оптимальный план решения задачи x* = (0, 115/11, 155/11, 0).По логике постановки задачи подразумеваются х1, х2, х3 и х4 целые числа, поэтому х2= 115/1110 единицы продукции — оптимальный выпуск продукции второго типа, а оптимальный выпуск продукции третьего типа равен х3 = 155/1114 единиц. При таком выпуске предприятие получит прибыль в размере: Z*= 50 * 10 + 40 * 14 = 1060 ден.

ед.Проверим выполнение ограничений задачи:

5* 0 + 4 * 10 + 2 * 14 + 5 * 0 = 68 <= 7044 * 0 + 28 * 10 + 36 * 14 + 60 * 0 = 784<= 80 011 * 0 + 15 * 10 + 8 * 14 + 17 * 0 = 262<= 400×1 0, х2 0, х3 0, х40Все ограничений выполнены.

4. Анализ полученных результатов

Полученное решение транспортной задачи исравнение его с исходными данными позволяет сделать вывод о том, что все запросы потребителей удовлетворены — требуемое количество груза доставлено каждому потребителю. Одновременно от поставщиков вывезены все запасы груза. От поставщика, А 10 тыс.

тонн передано потребителю К, 20 тыс.

тонн — потребителю М, по 70 тыс.

тонн потребителям Н и Р. От поставщика Д все 270 тыс.

тонн передано потребителю Л. От поставщика Е 170 тыс.

тонн передано потребителю К, 30 тыс.

тонн — потребителю Л. При этом достигнут оптимальный план перевозок по критерию времени, т.к. выбраны наиболее короткие интервалы движений, а, следовательно, план оптимален и по критерию затрат, т.к. позволяет сократить транспортные расходы по сравнению с перевозками по неоптимизированному плану поставок. Перевозка по оптимальному плану составит путь в 1185 км или в 143 750 т-км.Полученное решение задачи оптимального плана выпуска продукции позволяет сделать вывод, что для получения максимальной прибыли при данных запасах ресурсов необходимо производить продукции второго вида в объеме около 11 единиц, продукции третьего вида в объеме 14 единиц, а продукциюпервого и четвертого вида не нужно производить вообще. При этом ресурсы второго и третьего (трудовые и технические возможности) видов используется полностью, а ресурсы первого вида (сырье и материалы) используются не полностью. При таком оптимальном плане выпуска (с учетом округления объемов выпуска до целых величин) предприятие получит максимальную прибыль в размере 1060 у.д.е. (50 * 10 + 40 * 14 = 1060).Список использованной литературы

Акулич И. Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. — М.: Высшая школа, 2005

Данко П.Е., Попов А. Г., Кожевникова Т. Я. Высшая математика в упражнениях и задачах: Учебное пособие для студентов втузов. — Ч.I. — М.: Высшая школа, 2007. — 304 с. Экономико-математические методы и прикладные модели / Под ред. В. В. Федосеева. — М.: ЮНИТИ, 2009

Андрейчиков А. В. Экономика, математические методы в задачах аналитического планирования. — Волгоград: Волгоград. гос. техн. ун-т, 2008

Экономико-математические методы и прикладные модели/ Под ред. В. В. Федосеева. — М.:Прогресс, 2007