![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Главная Рефераты по сексологии Рефераты по информатике программированию Рефераты по биологии Рефераты по экономике Рефераты по москвоведению Рефераты по экологии Краткое содержание произведений Рефераты по физкультуре и спорту Топики по английскому языку Рефераты по математике Рефераты по музыке Остальные рефераты Рефераты по авиации и космонавтике Рефераты по административному праву Рефераты по безопасности жизнедеятельности Рефераты по арбитражному процессу Рефераты по архитектуре Рефераты по астрономии Рефераты по банковскому делу Рефераты по биржевому делу Рефераты по ботанике и сельскому хозяйству Рефераты по бухгалтерскому учету и аудиту Рефераты по валютным отношениям Рефераты по ветеринарии Рефераты для военной кафедры Рефераты по географии Рефераты по геодезии Рефераты по геологии Рефераты по геополитике Рефераты по государству и праву Рефераты по гражданскому праву и процессу Рефераты по делопроизводству Рефераты по кредитованию Рефераты по естествознанию Рефераты по истории техники Рефераты по журналистике Рефераты по зоологии Рефераты по инвестициям Рефераты по информатике Исторические личности Рефераты по кибернетике Рефераты по коммуникации и связи |
Учебное пособие: Практикум по решению линейных задач математического программированияУчебное пособие: Практикум по решению линейных задач математического программированияПРАКТИКУМ ПО РЕШЕНИЮ ЛИНЕЙНЫХ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Введение Математическое программирование – это раздел математики, который изучает теорию и методы поиска лучших вариантов планирования хозяйственной деятельности человека как на одном определенном предприятии, так и в некоторой отрасли или в отдельном регионе, или в целом государстве. Лучшие варианты – это те, при которых достигается максимальная производительность труда, минимум себестоимости, максимальная прибыль, минимум использования ресурсов и т.д. С точки зрения математики – это класс оптимизационных задач. Основным инструментом при их решении является математическое моделирование. Математическая модель – это формальное описание изучаемого явления и «перевод» всех существующих сведений о нем на язык математики в виде уравнений, тождеств, неравенств. Если все эти соотношения линейные, то вся задача называется задачей линейного программирования (ЗЛП). Критерием эффективности этой модели является некоторая функция, которую называют целевой. Постановка задачи линейного программирования и формы ее записи Сформулируем общую задачу линейного программирования. Пусть дана система m линейных уравнений и неравенств с n переменными (система ограничений):
и линейная функция
Необходимо
найти такое решение В общем
случае ЗЛП может иметь бесконечное множество решений. Часто решение Оптимальным
решением
или оптимальным планом задачи линейного программирования называется
такое ее решение
Здесь: Пример. Составить экономико-математическую модель задачи: Для выпуска изделий двух типов А и В на заводе используют сырье четырех видов (I, II, III, IV). Для изготовления изделия А необходимо: 2 ед. сырья первого вида, 1 ед. второго вида, 2 ед. третьего вида и 1 ед. четвертого вида. Для изготовления изделия В требуется: 3 ед. сырья первого вида, 1 ед. второго вида, 1 ед. третьего вида. Запасы сырья составляют: I вида – 21 ед., II вида – 8 ед., III вида – 12 ед., IV вида – 5 ед. Выпуск одного изделия типа А приносит 3 УДЕ прибыли, а одного изделия типа В – 2 УДЕ. Составить план производства, обеспечивающий наибольшую прибыль. Решение. Достаточно часто при составлении математической модели экономической задачи бывает удобно данные условия представить в виде таблицы:
Пусть Тогда прибыль составит: Составим систему ограничений, используя заданную
ограниченность сырья. При планируемых объемах производства расходуется сырья I вида: Получаем математическую модель задачи линейного программирования: Пример. Составить математическую модель задачи: На четырех станках (I, II, III, IV) обрабатываются два вида деталей (А и В). Каждая деталь проходит обработку на всех станках. Известны время обработки деталей на каждом станке, время работы станков в течение одного цикла производства и прибыль, полученная от выпуска одной детали. Данные приведены в таблице:
Составить план производства, обеспечивающий наибольшую прибыль при условии, что количество деталей вида В не должно быть меньше количества деталей вида А. Решение. Пусть Тогда математическая модель задачи линейного программирования имеет вид: Любая ЗЛП может быть сведена к канонической, стандартной или общей задаче. Приведение задач к каноническому виду Пусть имеем
задачу общего вида, которую нужно привести к каноническому виду, т.е. из
ограничений-неравенств сделать ограничения-равенства. Для этого в каждое
ограничение вводится дополнительная неотрицательная балансовая переменная со
знаком «+», если знак неравенства « Примечание: 1) В канонической форме
равенства принято записывать так, чтобы правые части ограничений были
неотрицательными. Если какое-либо 2) Если ограничение содержит знак «=», то дополнительную переменную вводить не нужно. Пример. Записать задачу линейного программирования в каноническом виде.
Решение. Второе
ограничение системы содержит в правой части отрицательное число –2. Умножим
второе ограничение на (–1), при этом знак неравенства
В первое и во
второе ограничения добавим по дополнительной переменной
Задания для самостоятельной работы. Составить экономико-математические модели следующих задач: 1. Для изготовления двух видов продукции P1 и Р2 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице: 2.
Прибыль, получаемая от единицы продукции Р1 и Р2, – соответственно 2 грн. и 3 грн. 3. На приобретение оборудования для нового производственного участка общей площадью 375 м2 предприятие обладает необходимым количеством денежных средств. Предприятие может заказать оборудование двух видов: машины первого типа стоимостью 10000 грн., требующие производительную площадь 6 м2 (с учетом проходов), производящие 4000 единиц продукции за смену, и машины второго типа стоимостью 20000 грн., занимающие 10 м2 площади, производящие 5000 единиц продукции за смену. Общая производительность данного производственного участка должна быть не менее 221000 единиц продукции за смену. Построить модель задачи при условии, что оптимальным для предприятия вариантом приобретения оборудования считается тот, который обеспечивает наименьшие общие затраты. 4. Фермер планирует произвести не менее 120 тонн пшеницы, 70 тонн кукурузы и 15 тонн гречихи. Для этого можно использовать два массива сельскохозяйственных угодий в 1000 и 800 га. В таблице приведены урожайность каждой культуры на различных участках (верхний показатель) и затраты на 1 га сельскохозяйственных угодий при производстве различных культур (нижний показатель). Требуется составить такой план засева, чтобы валовой сбор зерна удовлетворял плановому заданию, а стоимость затрат была наименьшей.
5. Фирма имеет возможность рекламировать свою продукцию, используя для этого телевидение, радио и газеты. Затраты на рекламу в бюджете фирмы ограничены суммой 8000 грн. в месяц. Опыт прошлых лет показал, что 1 грн., потраченная на телерекламу, дает фирме прибыль в размере 10 грн., а потраченная на рекламу по радио и в газетах – соответственно 4 и 8 грн. Фирма намерена затратить на теле- и радиорекламу не более 70% рекламного бюджета, а затраты на газетную рекламу не должны больше чем вдвое превышать затраты на радиорекламу. Определить такой вариант распределения рекламного бюджета по разным направлениям рекламы, который дает фирме наибольшую прибыль от рекламы своей продукции. 6. Продукция фабрики выпускается в виде бумажных рулонов стандартной ширины – 2 м. По специальным просьбам потребителей фабрика поставляет также рулоны других размеров, разрезая стандартные рулоны. Типичные заявки на рулоны нестандартных размеров приведены в таблице:
Определить оптимальный вариант раскроя стандартных рулонов, при котором все поступающие специальные заявки будут выполнены при минимальных затратах бумаги. Графический метод решения задач линейного программирования1. Область решений линейных неравенств.Пусть задано
линейное неравенство с двумя переменными
Если величины
Пример 1. Найти полуплоскость, определяемую неравенством
Решение. Строим
прямую Подставим Пример 2. Найти полуплоскость, определяемую неравенством
Решение.
Строим прямую 2. Область решений системы линейных неравенств.Пример. Найти область решений системы неравенств: Решение. Находим область решений I-го неравенства (рис. 1) и II-го неравенства (рис. 2). Все точки части плоскости, где штриховка наложилась, будут удовлетворять и первому и второму неравенству. Таким образом, получена область решений заданной системы неравенств (рис. 3). Если к
заданной системе неравенств добавить условия Принцип нахождения решения системы линейных неравенств не зависит от количества неравенств, входящих в систему. Примечание: Область допустимых решений (ОДР) если существует, то представляет собой замкнутый или незамкнутый выпуклый многоугольник. 3. Алгоритм графического метода решения ЗЛПЕсли задача линейного программирования содержит только две переменные, то ее можно решить графическим методом, выполняя следующие операции: 1) Строим все полуплоскости, соответствующие ограничениям системы. 2) Находим область допустимых решений (ОДР), как множество точек, в котором пересекаются все построенные полуплоскости. 3)
Строим
вектор 4)
Перпендикулярно
вектору 5)
Перемещаем
линию уровня 6)
Находим
координаты 7) Подставляем эти координаты в целевую функцию и находим ее max (или min). Пример. Решить задачу линейного программирования графическим методом
Решение.
Третье и четвертое ограничения системы – двойные неравенства, преобразуем их к
более привычному для подобных задач виду Т.о. задача примет вид
Заменив знаки неравенств на знаки точных равенств, построим область допустимых решений по уравнениям прямых:
Областью решений неравенств является пятиугольник ABCDE. Построим
вектор
Подставим
координаты точки С в целевую функцию и найдем ее максимальное значение
Решение.
Область допустимых решений – открытая область (рис. 6). Линия уровня Задания для самостоятельной работы. 1. Найти область решений системы неравенств: а) 2. Решить графически задачу линейного программирования
3. Составить экономико-математическую модель и решить графически задачу линейного программирования Фирма выпускает изделия двух видов А и В. Изделия каждого вида обрабатывают на двух станках (I и II). Время обработки одного изделия каждого вида на станках, время работы станков за рабочую смену, прибыль фирмы от реализации одного изделия вида А и вида В занесены в таблицу:
Изучение рынка сбыта показало, что ежедневный спрос на изделия вида В никогда не превышает спрос на изделия вида А более чем на 40 единиц, а спрос на изделия вида А не превышает 90 единиц в день. Определить план производства изделий, обеспечивающий наибольшую прибыль. Симплексный метод решения задач линейного программирования Симплексный метод – это метод последовательного улучшения плана. Этим методом можно решать задачи линейного программирования с любым количеством переменных и ограничений. Этот метод включает в себя три основные этапа: 1) Построение начального опорного плана. 2) Правило перехода к лучшему (точнее, нехудшему) решению. 3) Критерий проверки найденного решения на оптимальность. При симплексном методе выполняются вычислительные процедуры (итерации) одного и того же типа в определенной последовательности до тех пор, пока не будет получен оптимальный план задачи или станет ясно, что его не существует. 1) Построение начального опорного плана.Данную задачу линейного программирования необходимо сначала привести к каноническому виду; при этом правые части ограничений должны быть неотрицательными. Признаком возможности построения начального опорного плана служит наличие в каждом ограничении-равенстве с неотрицательной правой частью базисной переменной. Базисной называют плановую переменную, которая входит только в одно уравнение (а в другие не входит), и при этом имеет коэффициент, равный единице. Пусть задача линейного программирования приведена к каноническому виду, и все уравнения системы ограничений имеют свою базисную переменную. Приравняв базисные переменные к соответствующим правым частям ограничений, а остальные переменные к нулю, получим опорное или базисное решение задачи. Пример. Для данной задачи линейного программирования найти начальный опорный план (базисное решение).
Решение. Изменим знаки второго и третьего неравенств на противоположные, умножив каждое из них на –1. Система ограничений теперь будет такой: В каждом
ограничении слева добавим положительную переменную
Переменные Запишем теперь начальный опорный план
2) Составление симплексных таблиц. Критерий оптимальности.Симплексный метод удобно применять, используя построение симплексных таблиц. Первая симплексная таблица, соответствующая начальному плану, имеет вид:
Здесь приняты следующие обозначения. Столбец «Базис» – это базисные переменные. Столбец « Столбец «В» правые части ограничений;
Последняя
строка в таблице (
Например,
Оценки ( Признак оптимальности опорного плана состоит в следующем: Опорный план будет оптимальным тогда и только тогда, когда все оценки
Если критерии оптимальности не выполняются, то нужно перейти к нехудшему опорному плану, т.е. исключить из базиса некоторую переменную и ввести вместо нее новую из числа свободных переменных. Переменная,
которую нужно ввести в базис, соответствует той оценке Для
определения переменной, которую нужно вывести из базиса, поступают так:
элементы столбца В делят только на положительные элементы разрешающего столбца
и находят симплексные отношения На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере. Пример. Решить симплексным методом задачу линейного программирования.
Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства.
2) Определяем
базисные переменные – это
Здесь Находим Наименьшее из
этих чисел – это число 5, что соответствует строке базисной переменной Заполнение
следующей таблицы начинаем со столбцов «Базис» и «
Или элемент Оценки
Свободные
(небазисные) переменные Итак,
Примечание: При переходе от таблицы
к таблице для контроля сравнивают При использовании симплексного метода возможны следующие случаи. 1) Если в
оценочной строке симплекс-таблицы оценка 2) Если при переходе от одного опорного плана к другому в разрешающем столбце нет положительных элементов, то это означает, что целевая функция ЗЛП является неограниченной и оптимальных планов не существует. Задания для самостоятельной работы. Определить оптимальный план задач, используя симплексный метод решения задач линейного программирования:
1) Симметричные двойственные задачиРассмотрим
задачу производственного планирования. Пусть предприятие имеет m видов ресурсов объемом План
производства
Или в краткой форме записи математическая модель задачи имеет вид:
Задачу (1) (3) называют исходной. По исходным данным задачи (1) – (3) сформируем другую экономическую задачу. Предположим,
что предприятию разрешено на его усмотрение реализовать все указанные ресурсы.
Необходимо установить цены на них – – покупатель стремится минимизировать их общую стоимость; – предприятие согласно продать по ценам, дающим прибыль не меньшую, чем выручка, которую оно может получить от реализации изготовленной продукции. Эти требования можно записать в виде следующей ЗЛП:
Или в краткой форме записи:
Полученную
задачу (4) – (6) называют двойственной. Переменные Задачи (1) (3) и (4) – (6) называют парой взаимно двойственных симметричных задач, т. к. они обладают следующими свойствами: 1. Если в одной задаче ищется максимум целевой функции, то в другой – минимум. 2. Коэффициенты при переменных в целевой функции одной задачи являются правыми частями ограничений другой задачи и, наоборот. 3.
В
каждой задаче система ограничений задается в виде неравенств, причем все они
одного смысла: если задача на max, то все неравенства содержат знаки « 4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу. 5. Число неравенств в системе ограничений одной задачи равно числу переменных другой задачи. 6. Условие неотрицательности переменных сохраняется в обеих задачах. Примечание: Понятие «прямой» и «двойственной» задач условно. 2) Построение модели двойственной задачиИспользуя свойства (1–6), покажем на конкретном примере построение двойственной задачи. Пример. Пусть исходная задача имеет вид:
Нужно составить к ней двойственную. Решение. Запишем расширенную матрицу системы ограничений и транспонируем ее.
Теперь
запишем двойственную задачу по АТ с переменными
Пример. К заданной задаче записать двойственную: Решение. Так
как задача на min, то все неравенства должны иметь знаки «
Запишем матрицы А и АТ.
Двойственная задача:
3) Применение теорем двойственности к анализу оптимальных решений пары симметричных двойственных задачРассмотрим следующую задачу. Предприятие планирует выпускать 3 вида продукции – П1, П2, П3. Для этого оно располагает объемами ресурсов 3-х видов Р1, Р2, Р3. Затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции приведены в таблице:
Требуется: 1) построить модель исходной и двойственной задач; 2) решить исходную задачу симплексным методом; 3) найти оптимальное решение двойственной задачи, используя проверочную строку последней симплексной таблицы; 4) дать экономический анализ основным и дополнительным переменным оптимальных решений обеих задач; 5) в ответе записать оптимальные решения обеих задач и значения их целевых функций; указать наиболее дефицитный ресурс и наиболее убыточный вид продукции. Решение. 1. Построим модель исходной задачи
Здесь х1, х 2, х3 – план выпуска продукции. Составим математическую модель двойственной задачи:
2. Решим исходную задачу симплексным методом. Запишем ее канонический вид:
Так как все
оценки
3. Найдем оптимальное решение двойственной задачи, используя последнюю проверочную строку симплексной таблицы и соотношение между переменными прямой и двойственной задач.
Откуда:
Таким образом
получили 4. Проанализируем основные и дополнительные переменные оптимальных решений обеих задач. Основные переменные исходной задачи – это планируемый выпуск продукции. Продукцию І-го вида к выпуску не планируют, ІІ-го вида – в количестве 82 ед. и ІІІ-го вида – в количестве 16 ед. Дополнительные переменные исходной задачи показывают остатки сырья. Сырье І и ІІІ видов израсходовано полностью. А сырье ІІ вида осталось в количестве 80 ед. Основные
переменные двойственной задачи характеризуют дефицитность сырья: если Таким образом, сырье І и ІІІ видов дефицитное, причем наиболее дефицитное сырье І-го вида. Сырье ІІ вида недефицитное. Дополнительные
переменные двойственной задачи характеризуют рентабельность продукции. При
этом, если По этому соотношению видно, что продукция І вида нерентабельна, а ІІ и ІІІ рентабельна. Ответ:
Наиболее дефицитное сырье І вида. Наиболее убыточный І вид продукции. Задания для самостоятельной работы. Для производства четырех видов продукции (П1, П2, П3, П4) используются три вида ресурсов. Норма затрат ресурсов, использованных для выпуска единицы продукции каждого вида, цена единицы продукции и запасы ресурсов приведены в таблице. Построить модель прямой и двойственной задач. Найти оптимальный план для обеих задач и экстремальные значения целевых функций. Дать экономическую интерпретацию основным и дополнительным переменным исходной и двойственной задач.
Транспортная задача возникает при планировании рациональных перевозок грузов. Математическая модель транспортной задачи в простейшем случае имеет вид:
Здесь:
Z – транспортные расходы;
Обычно транспортную задачу задают тремя матрицами: матрицей поставщиков, матрицей потребителей и матрицей тарифов. Для наглядности транспортную задачу представляют в виде распределительной таблицы. Любая
транспортная задача имеет допустимое решение (матрицу перевозок
Если условие (4) выполняется, то транспортную задачу называют транспортной задачей закрытого типа. Допустимое решение транспортной задачи часто называют планом перевозок. 1) Построение начального опорного плана. Его вырожденность или невырожденность. Ранг матрицы системы.а) Метод северо-западного угла.Заполнение
распределительной таблицы начинают с клетки (1; 1), при этом Пример. Построить методом
северо-западного угла начальный опорный план для транспортной задачи: поставщики
а = (20; 30; 40); потребители Найти стоимость перевозок. Решение. Строим распределительную таблицу и находим груз х11 = min (20; 15) = 15. По первому столбцу не перемещаемся, так как спрос І потребителя удовлетворен. Перемещаемся по І строке в клетку (1; 2): х12 = min (а1 х11; b2) = min (5; 35) = 5. Теперь переходим по ІІ столбцу в клетку (2; 2): х22 = min (30; b2 – х12) = min (30; 30) = 30. Так как спрос ІІ потребителя удовлетворен и у ІІ поставщика продукция уже выбрана, то переходим к клетке (3; 3): х33 = min (40; 20) = 20. х34 = min (а3 х33; b4) = min (20; 20) = 20. Таким образом, получен план перевозок:
Для подсчета стоимости перевозок нужно количество груза в каждой заполненной клетке умножить на соответствующий тариф в этой клетке и результаты сложить.
б) Метод минимального элемента (наименьшей стоимости).Строим распределительную таблицу и начинаем ее заполнять с той клетки, в которой наименьший тариф. Пример. Построить начальный
опорный план методом минимальной стоимости и найти транспортные расходы для транспортной
задачи: поставщики а = (20; 30; 40); потребители Решение. Строим распределительную таблицу и начинаем ее заполнять с клетки (2; 1), т. к. в ней наименьший тариф х21 = min (30; 15) = 15.
Потом заполняем клетку (3; 2) с тарифом с32 = 3; х32 = min (40; 35) = 35. Далее х33 = min (а3 – х32; b3) = (5; 20) = 5; х14 = min (20; 20) = 20; х23 = min (а2 х21; b3 – х33) = min (15; 15) = 15.
Сравнивая значение Z в а) и б), видим, что учитывая стоимости перевозок, затраты при втором методе значительно меньше. Рангом
матрицы системы (2) называют число В пунктах а)
и б) 2) Метод потенциалов. Признак оптимальности опорного плана.Допустимое
решение транспортной задачи является оптимальным тогда и только тогда, когда
можно найти такие числа – потенциалы I.
II.
III. На основании
первого условия оптимальности потенциалы находят из условий Если при проверке
второго условия оптимальности окажется, что 3) Переход к нехудшему опорному плану.Переход к не худшему опорному плану осуществляют при помощи цикла перераспределения груза. Цикл представляет собой замкнутую ломаную, звенья которой взаимно перпендикулярны и вершины цикла, кроме одной, находятся в заполненных клетках. Приведем примеры разновидностей форм циклов: В каждом
случае только одна вершина цикла находится в незаполненной клетке. Ее называют
началом цикла и определяют по наибольшему нарушению условия оптимальности (6), т.е.
по максимальной оценке Таким образом, получаем новый опорный план. Подсчитываем транспортные расходы, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяем на оптимальность, используя условия (5) и (6). Если план оптимальный, то задача решена. Если же план опять не оптимальный, то работаем, согласно пункту 3) до получения оптимального плана и нахождения Zmin. Транспортная задача открытого типаЕсли для транспортной задачи выполняется одно из условий
то модель
задачи называют открытой. Чтобы такая задача имела решение, необходимо
ее привести к закрытому типу, т.е. чтобы выполнялось равенство Это делают
так: если Запишем алгоритм решения транспортной задачи: 1) Проверка типа модели ТЗ. 2) Построение начального опорного плана (любым способом). 3) Проверка плана на вырожденность. 4) Проверка плана на оптимальность методом потенциалов: а) нахождение потенциалов из системы
б) проверка второго условия оптимальности
5) Переход к нехудшему опорному плану (если это необходимо). Пример. На складах имеются запасы однотипного товара в количестве а (35; 40; 40; 50), который необходимо доставить потребителям. Потребности потребителей задает вектор b (31; 52; 17; 20). Матрица затрат на доставку единицы товара от i-го поставщика j-му потребителю: с= Составить план перевозок с минимальными транспортными затратами. Решение.
Определим тип модели транспортной задачи. Суммарная мощность поставщиков: Т.к. Введем фиктивного потребителя, спрос которого равен
Тарифы
Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план является невырожденным. Транспортные затраты, соответствующие опорному плану:
Исследуем опорный план на оптимальность, используя метод потенциалов. Дополним таблицу 1 столбцом и строкой
потенциалов
Из записанной системы находим: Проверим выполнение второго условия
оптимальности. Для всех пустых клеток должно выполняться неравенство: (1; 1) (1; 2) (1; 5) (2; 3) (2; 4) (2; 5) (3; 1) (3; 2) (3; 3) (3; 4) (4; 1) (4; 4) Т.к. среди свободных клеток есть такие, в которых второе условие оптимальности не выполняется, то план не оптимален. Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (4; 4), т. к. ей соответствует наибольшая положительная оценка
Найдем цикл перераспределения груза для этой клетки. Выбранной для заполнения клетке присваиваем знак «+», далее знаки чередуем. Среди вершин со знаком «–» выбираем наименьшую поставку.
Перераспределим поставки по циклу, тем самым перейдем к новому опорному плану.
Исследуем опорный план на оптимальность.
Найдем значения потенциалов, используя первое условие оптимальности. Для заполненных
поставками клеток
Проверим выполнение второго условия
оптимальности. Для всех пустых клеток должно выполняться неравенство: Выпишем клетки, в которых условие нарушено: (1; 2) Осуществим переход к нехудшему опорному
плану. Наиболее перспективная для заполнения клетка (1; 2), т. к. ей
соответствует положительная оценка
Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план (таб. 3) является невырожденным.
Транспортные затраты, соответствующие опорному плану:
Исследуем опорный план на оптимальность. Найдем значения потенциалов, используя
первое условие оптимальности. Для заполненных поставками клеток
Проверим выполнение второго условия
оптимальности. Для всех пустых клеток должно выполняться неравенство: Второе условие оптимальности выполняется для всех свободных клеток, следовательно, план оптимален. Наименьшие транспортные затраты Ответ: Задания для самостоятельной работы. Составить план перевозок с минимальными транспортными затратами.
При решении оптимизационных экономических задач необходимо пройти через следующие этапы: · Составить математическую модель экономической задачи; · Решить полученную экстремальную математическую задачу; · Дать экономическую интерпретацию ответу. Рассмотрим прохождение этих этапов на примере задачи об использовании ресурсов. Пример. Для изготовления изделий двух видов А и В на заводе используют сырье четырех типов (І, ІІ, ІІІ, IV). Для выпуска изделия А необходимо 2 единицы сырья І типа; 1 ед. сырья ІІ типа; 2 ед. сырья ІІІ типа; 1 ед. сырья IV типа. Для изготовления изделия В требуется 3 единицы сырья І типа; 1 ед. сырья ІІ типа; 1 ед. сырья ІІІ типа. Запасы сырья составляют: І типа – 21 ед., ІІ типа – 8 ед., ІІІ типа – 12 ед., IV типа – 5 ед. Выпуск одного изделия типа А приносит 3 грн. прибыли, а одного изделия типа В – 2 грн. прибыли. Составить план производства, обеспечивающий наибольшую прибыль. Решение. · Составление математической модели. Вопрос задачи, сформулированный в виде «составить план производства, обеспечивающий наибольшую прибыль», означает, что необходимо определить, какое количество изделий А и В нужно производить (для достижения наибольшей прибыли). Так как необходимо определить количество изделий А и В, то введем следующие обозначения:
Z (целевая функция задачи) по своему экономическому смыслу – это прибыль. (Т.к. из условия задачи мы видим, что слово «наибольшая», связанное с экстремумом, соответствует прибыли). Получим:
· Решение полученной экстремальной задачи: Для решения задачи воспользуемся возможностями Microsoft Excel. § Откройте Microsoft Excel. §
В
ячейки первой строки (в данном случае А1 и В1) введите обозначения имеющихся в
задаче переменных §
В
ячейки второй строки (в данном случае А2 и В2), соответствующие заполненным
ячейкам первой, введите произвольные значения переменных (для простоты возьмем
значения 1, хотя на самом деле это могут быть любые числа). Тем самым мы
присваиваем В ячейку А4 введите обозначение целевой функции Z=. § В ячейку В4 введите формулу вычисления целевой функции из математической модели задачи ( После нажатия
кнопки Enter на экране монитора должно быть следующее. (Продумайте, как изменится
картинка, если ввести иные значения В ячейки А5 и В5 введите соответственно слова: А5 – Ограничение, В5 – Правая часть ограничения. §
В
ячейку А6 введите формулу вычисления левой части первого ограничения § В ячейку В6 введите свободный член первого ограничения – 21. После нажатия кнопки Enter на экране монитора должно быть следующее. §
Аналогично
в ячейку А7 введите формулу вычисления левой части второго ограничения § После нажатия кнопки Enter на экране монитора должно быть следующее. Таким образом, мы ввели все данные условия задачи в компьютер и подготовились к тому, чтобы задачу решить. § В меню Сервис выберите команду Поиск решения (именно она является инструментом для поиска решений задач оптимизации) § В этой команде вам будет предложено установить целевую ячейку. Именно слово «целевую» поможет вам в дальнейшем вспомнить, о чем идет речь. Конечно же, о значении целевой функции. Введите это значение, щелкнув левой кнопкой мышки на ячейке В4 (содержащей в данном случае числовое значение целевой функции). Получите: §
Если решаем задачу на минимум, то нужно поставить метку • перед словами минимальному значению. § Далее нажмите на стрелку, расположенную в правой части пространства ячейки Изменяя ячейки:, в результате чего на экране должно появиться следующее В полученное
пространство необходимо ввести диапазон изменяющихся в задаче переменных (т.е. ячейки,
содержащие числовые значения Т.е. заполненная ячейка должна принять вид: § После этого заполняют пространство ячейки Ограничения: Для чего нужно щелкнуть по кнопке Добавить, в результате чего на экране появится новое окно: В Ссылка на ячейку: введите номер ячейки, содержащей левую часть ограничения (в данном случае для первого ограничения – это ячейка А6). Выберите знак
ограничения в соответствии с математической моделью из предлагаемых вариантов
(в данном случае <=, т. к. первое ограничение со знаком В Ограничение: введите номер ячейки, содержащей свободный член ограничения (в данном случае для первого ограничения – это ячейка В6). Т.о. перед вами на экране должна быть следующая картинка: Это вы ввели только первое ограничение, а есть еще и другие, поэтому нажмите кнопку Добавить и аналогичным образом введите второе, третье и четвертое ограничения. §
Но
после того, как все ограничения системы введены, еще рано нажимать ОК,
т. к. в математической модели имеется условие неотрицательности переменных
( Поэтому после
введения последнего ограничения вновь нажмите кнопку Добавить и в
Ссылка на ячейку: введите номер ячейки, содержащей числовое
значение Еще раз
нажмите Добавить и аналогичным образом создайте условие неотрицательности
для § Таким образом, компьютер получил все те ограничения, которые есть в условии задачи, поэтому теперь можно нажать ОК. В результате на экране появится следующее: Появилось? Если ДА, то нажимайте Выполнить. И согласитесь на то, чтобы Сохранить найденное решение. Т.е. в появившемся окне нажмите ОК. §
Обратите
внимание на то, какие теперь значения принимают
экстремальное
значение целевой функции ( Математически задача решена. Осталось дать экономическую интерпретацию полученному. · Дадим экономическую интерпретацию ответу. Для достижения наибольшей прибыли 20 грн. необходимо производить 4 изделия А и 4 изделия В. Литература 1. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування. – К.: КНЕУ, 2001. 2. Исследование операций в экономике/ Под ред. проф. Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 2000. 3. Конюховский П.В. Математические методы исследования операций в экономике: учебное пособие. – СПб. – Москва Харьков – Минск, 2005. 4. Кулян В.Р. и др. Математическое программирование. – К.: МАУП, 2005. 5. Таха, Хемди. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2001. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||