 ПОЗНАВАТЕЛЬНОЕ Сила воли ведет к действию, а позитивные действия формируют позитивное отношение Как определить диапазон голоса - ваш вокал Игровые автоматы с быстрым выводом Как самому избавиться от обидчивости Противоречивые взгляды на качества, присущие мужчинам Вкуснейший "Салат из свеклы с чесноком" Натюрморт и его изобразительные возможности Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д. Как научиться брать на себя ответственность Зачем нужны границы в отношениях с детьми? Световозвращающие элементы на детской одежде Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия Классификация ожирения по ИМТ (ВОЗ) Глава 3. Завет мужчины с женщиной
Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.
| МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Математическое программирование ("планирование") – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Идея линейного программирования возникла в 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Дальнейшее изложение материала предполагает, что студенты изучали теорию линейного программирования в курсе математики. В связи с этим рекомендуется совмещать чтение этой главы с просмотром презентаций. Электронные версии презентаций размещены в папке «Линейное программирование». При этом часть материала предназначена для восстановления знаний, полученных в курсе математики, а часть для их расширения и углубления с акцентом на прикладные возможности теоретических моделей. Теория линейного программирования Общая постановка задачи Идея линейного программирования представлена в формате презентаций, электронная версия которых размещена в файле «Идея - линейное программирование». Геометрическая интерпретация и графический метод решения Графически способ решения задач линейного программирования целесообразно использовать: 1. Для решения задач с двумя переменными, когда ограничения выражены неравенствами. 2. Решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных. Геометрический метод решения задач линейного программирования представлен в формате презентации - файл «Геометрический метод ЛП» 2.2. Симплекс-метод, общая характеристика, критерий оптимальности допустимого базисного плана Графический способ решения задачи линейного программирования показывает, что оптимальное решение этой задачи всегда ассоциируется с угловой точкой пространства решений (в математике она также называется крайней точкой множества). Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования. Переход от геометрического способа решения задачи линейного программирования к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу линейного программирования к стандартной (канонической) форме: · преобразовать неравенства ограничений в равенства путем введения дополнительных переменных; · преобразовать свободные переменные в неотрицательные; · преобразовать задачу максимизации в задачу минимизации. Стандартная форма задачи линейного программирования необходима, потому что она позволяет получить базисное решение (используя систему уравнений, порожденную ограничениями). Это (алгебраическое) базисное решение полностью определяет все (геометрические) крайние точки пространства решений. Симплекс-метод позволяет эффективно найти оптимальное решение среди всех базисных. Восстановить знания по решению задач симплекс-методом можно с помощью презентации «Симплекс метод». Двойственные задачи Любая задача линейного программирования имеет двойственную природу. Правило построения двойственной задачи: • Если исходная задача на max, то двойственная на min и наоборот. • В двойственной задаче столько переменных, сколько ограничений в исходной постановке. При этом переменные соответствуют ограничениям и наоборот. • Коэффициентами целевой функции двойственной задачи являются правые части ограничений исходной задачи. • Матрица коэффициентов ограничений двойственной задачи получается транспонированием матрицы коэффициентов ограничений исходной задачи. • Правыми частями ограничений двойственной задачи являются коэффициенты целевой функции исходной. • Ограничениям неравенствам исходной задачи соответствуют неотрицательные переменные двойственной задачи, а ограничениям равенствам – переменные любого знака и наоборот. Теорема 1: Если исходная задача имеет оптимальный план x*, то двойственная задача также имеет оптимальный план y*, причем значения функций на этих планах равны: f(x*)=g(y*). Теорема 2: Если исходная и двойственная задачи имеют планы, то они имеют и оптимальные планы, причем f(x*)=g(y*). Признаки оптимальности для двойственных задач: Признак 1: Если исходная и двойственная задачи имеют планы X и Y, причем f(X)=g(Y), то эти планы оптимальные. Определение: Ограничения, расположенные на одной строке в схеме пары двойственных задач, называют сопряженными. Признак 2: Для того, чтобы планы X и Y исходной и двойственной задач были оптимальны, необходимо и достаточно чтобы на этих планах хотя бы одно из каждой пары сопряженных ограничений являлось равенством. Второй признак позволяет, зная оптимальный план одной из задач, найти оптимальный план другой задачи. Основные положения двойственной задачи изложены в презентациях «Теория двойственности» и «Двойственная задача». Транспортные задачи Транспортная задача является одной из наиболее распространенных специальных задач линейного программирования. Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, а первый точный метод решения разработан Л. В. Канторовичем и М. К. Гавуриным. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов. Различают два типа транспортных задач: по критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени). Наиболее часто встречаются следующие задачи, относящиеся к транспортным: · прикрепление потребителей ресурса к производителям; · привязка пунктов отправления к пунктам назначения; · взаимная привязка грузопотоков прямого и обратного направлений; · отдельные задачи оптимальной загрузки промышленного оборудования; · оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др. Постановки задач транспортного типа, алгоритмы их решения и примеры практического использования представлены в трех презентациях: 1. «Обобщенная транспортная задача (λ-задача)». 2. «Закрытая транспортная задача. Метод потенциалов». 3. «Усложнённые постановки транспортной задачи». Экономические приложения Многообразие экономических приложений математического моделирования методами линейного программирования рассмотрим на примерах формулирования конкретных постановок прикладных задач (заимствовано из курса лекций Диязитдиновой А.П.). Задача 1 Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П1 и П2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед. Стоимость 1 ед. продукта П1 – 2 руб., П2 –3 руб. Постройте математическую модель задачи, позволяющую так организовать питание, чтобы его стоимость была минимальной, а организм получил необходимое количество питательных веществ. Задача 2 Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие:
Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров? Задача 3 Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 тонны. Овощехранилища имеют соответственно 20, 20 ,15 и 25 тонн. Тарифы (в д.е. за 1 тонну) указаны в следующей таблице:
Составьте план перевозок, минимизирующий суммарные транспортные расходы. Задача 4 Имеются два склада готовой продукции: А1 и А2 с запасами однородного груза 200 и 300 тонн. Этот груз необходимо доставить трем потребителям В1, В2 и В3 в количестве 100, 150 и 250 тонн соответственно. Стоимость перевозки 1 тонны груза из склада А1 потребителям В1, В2 и В3 равна 5, 3 ,6 д.е., а из склада А2 тем же потребителям – 3, 4, 2 д.е. соответственно. Составьте план перевозок, минимизирующий суммарные транспортные расходы. Задача 5 При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице.
Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е. Составьте дневной рацион питательности, имеющий минимальную стоимость. Задача 6 Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции: П1 , П2, П3 и П4. Организация производства характеризуется следующей таблицей:
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль. Задача 7. Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа – 3 тонны, проволоки – 18 тонн. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 4 д.е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль. Задача 8 Совхоз отвел три земельный массива размером 5000, 8000 и 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей таблице:
За 1 центнер ржи совхоз получает 2 д.е., за 1 центнер пшеницы – 2,8 д.е., за 1 центнер кукурузы – 1,4 д.е. Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1900 тонны ржи, 158 000 тонны пшеницы и 30 000 тонн кукурузы? Задача 9 Из трех продуктов – I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице:
Составьте наиболее дешевую смесь. Задача 10 В школе проводится конкурс на лучшую стенгазету. Одному школьнику дано следующее поручение: купить акварельной краски по цене 30 д.е. за коробку, цветные карандаши по цене 20 д.е. за коробку, линейки по цене 12 д.е., блокноты по цене 10 д.е.; красок нужно купить не менее трех коробок, блокнотов – столько, сколько коробок карандашей и красок вместе, линеек не более пяти. На покупки выделяется не менее 300 д.е. В каком количестве школьник должен купить указанные предметы, чтобы общее число предметов было наименьшим? Задача 11 Имеются три специализированные мастерские по ремонту двигателей. Их производственные мощности равны соответственно 100, 700, 980 ремонтов в год. В пяти районах, обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 90, 180, 150, 120, 80 двигателей в год. Затраты на перевозу одного двигателя из районов к мастерским следующие:
Спланируйте количество ремонтов каждой мастерской для каждого из районов, минимизирующее суммарные транспортные расходы. Задача 12 Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 120 д.е., 100 д.е., 150 д.е. Составьте план выпуска разных сортов авиационного бензина из условия получения максимальной стоимости всей продукции. Задача 13 Для участия в соревнованиях спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов. Соревнования проводятся по Буге, пряжкам в высоту, прыжкам в длину. В беге должны участвовать 5 спортсменов, в прыжках в длину – 8 спортсменов, а в прыжках в высоту – не более 10. количество очков, гарантируемых спортсмену каждого разряда по каждому виду, указано в таблице:
Распределите спортсменов в команды так, чтобы сумма очков команды была наибольшей, если известно, что в команде I разряд имеют только 10 спортсменов. Задача 14 Звероферма выращивает черно-бурых лисиц и песцов. На звероферме имеется 10 000 клеток. В одной клетке могут быть либо 2 лисицы, либо 1 песец. По плану на ферме должно быть не менее 3000 лис и 6000 песцов. В одни сутки необходимо выдавать каждой лисе корма – 4 ед., а каждому песцу – 5 ед. Ферма ежедневно может иметь не более 200 000 единиц корма. От реализации одной шкурки лисы ферма получает прибыль 10 д.е., а от реализации одной шкурки песца – 5 д.е. Какое количество лисиц и песцов нужно держать не ферме, чтобы получить наибольшую прибыль? Задача 15 Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 тонн зерна. Зерна необходимо перевезти трем хлебозаводам в количестве 1000, 2000 и 1600 тонн каждому. Расстояние от элеватора до хлебозавода указано в следующей таблице:
Затраты на перевозку 1 тонны продукта на 1 км составляют 25 д.е. Спланируйте перевозки зерна из условия минимизации транспортных расходов. Задача 16 Из двух сортов бензина образуются две смеси – А и В. Смесь А содержит Бензина 60% 1-го сорта и 40% 2-го сорта; смесь В – 80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А – 10 д.е., а смеси В – 12 д.е. Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется бензин 50 т 1-госорта и 30 т второго сорта. Задача 17 Имеются две почвенно-климатические зоны, площади которых соответственно равны 0,8 и 0,6 млн. га. Данные об урожайности зерновых культур приведены в таблице:
Определите размеры посевных площадей озимых и яровых культур, необходимые для достижения максимального выхода продукции в стоимостном выражении. Задача 18 На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех видов: энергия, материалы, труд. Данные о технологическом процессе приведены в следующей таблице:
Спланируйте производство так, чтобы прибыль от их реализации была наибольшей. |
