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

В нашем примере это получение максимальной прибыли от реализации произведенной продукции. Если обозначить функцию размера прибыли через 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<= 80011х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х5705425100х680044283660010х74001115817001Z0-60-50-40-32000В последней строке имеем 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х7x11414/52/511/500x61840-36/592/516-44/510x7246031/518/56-11/501Z8400-2-16281200Далее ищем разрешающие столбец и строку в таблице 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х7x110122/23015/239/23-1/460x3100-9/23120/23-11/235/920x72100175/23066/23-11/23-9/461Z10000-190/230964/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х7x2115/1123/221015/229/22-1/440x3155/119/220125/22-7/221/220x71435/11-175/2200-51/22-79/22-1/441Z11950/1195/1100523/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<= 80011 * 0 + 15 * 10 + 8 * 14 + 17 * 0 = 262<= 400х1 0, х2 0, х3 0, х40Все ограничений выполнены.4. Анализ полученных результатовПолученное решение транспортной задачи исравнение его с исходными данными позволяет сделать вывод о том, что все запросы потребителей удовлетворены – требуемое количество груза доставлено каждому потребителю. Одновременно от поставщиков вывезены все запасы груза. От поставщика А 10 тыс.тонн передано потребителю К, 20 тыс.тонн – потребителю М, по 70 тыс.тонн потребителям Н и Р. От поставщика Д все 270 тыс.тонн передано потребителю Л. От поставщика Е 170 тыс.тонн передано потребителю К, 30 тыс.тонн – потребителю Л. При этом достигнут оптимальный план перевозок по критерию времени, т.к. выбраны наиболее короткие интервалы движений, а, следовательно, план оптимален и по критерию затрат, т.к. позволяет сократить транспортные расходы по сравнению с перевозками по неоптимизированному плану поставок.Перевозка по оптимальному плану составит путь в 1185 км или в 143750 т-км.Полученное решение задачи оптимального плана выпуска продукции позволяет сделать вывод, что для получения максимальной прибыли при данных запасах ресурсов необходимо производить продукции второго вида в объеме около 11 единиц, продукции третьего вида в объеме 14 единиц, а продукциюпервого и четвертого вида не нужно производить вообще. При этом ресурсы второго и третьего (трудовые и технические возможности) видов используется полностью, а ресурсы первого вида (сырье и материалы) используются не полностью.При таком оптимальном плане выпуска (с учетом округления объемов выпуска до целых величин) предприятие получит максимальную прибыль в размере 1060 у.д.е. (50 * 10 + 40 * 14 = 1060).Список использованной литературыАкулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. – М.: Высшая школа, 2005.Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах: Учебное пособие для студентов втузов. – Ч.I. – М.: Высшая школа, 2007. – 304 с.Экономико-математические методы и прикладные модели / Под ред. В.В. Федосеева. – М.: ЮНИТИ, 2009.Андрейчиков А. В. Экономика, математические методы в задачах аналитического планирования. – Волгоград: Волгоград. гос. техн. ун-т, 2008.Экономико-математические методы и прикладные модели/ Под ред. В. В. Федосеева. – М.:Прогресс, 2007