Скачать 0.57 Mb.
|
Метод линейного программирования – это нахождение максимума и минимума линейной функции от нескольких переменных при заданных дополнительно ограничениях для переменных Объяснение темы: Рассмотрим пример. Найти числа х1 и х2, которые удовлетворяют системе ограничений: ,при которых функция F(х1, х2) = 2х1 + 3х2 принимает максимальное значение Допустим, решением приведенной задачи называется пара чисел, удовлетворяющая всем ограничениям задачи. Оптимальным решением называется решение, при котором функция F принимает максимальное значение. Построим область допустимых значений задачи. Этой областью будет ОМ1М2М3. Нам нужно из этой области ОМ1М2М3 найти пару чисел х1, х2, при которых функция F(х1, х2) = 2х1 + 3х2 принимает максимальное значение. Пусть 2х1 + 3х2 = 0, тогда . Построим график зависимости . Осуществим теперь параллельный перенос его вверх вдоль оси Ох2 (это будет равносильно увеличению значений выражения 2х1 + 3х2 ). Последней точкой, которая будет общей у переносимого графика и у многоугольника ОМ1М2М3 будет точка М2, являющаяся пересечением прямых 2х1 + 5х2 = 10 и х1+х2 = 3 Решая систему найдем F(х1, х2)= В практических задачах функция F называется целевой или производственной, а многоугольник типа ОМ1М2М3 – многоугольником ограничений. Методические рекомендации Многие практические задачи сводятся к системам неравенств относительно нескольких переменных. Обычно задачи с планированием производства формулируются так: найти наилучший план производства при заданных ресурсах, которые, как правило, задаются при помощи ряда неравенств. В итоге приходится искать наибольшее или наименьшее значение некоторой функции в области, которая задается системой неравенств. Задачи такого рода относятся к задачам линейного программирования. Умение составлять план решения (алгоритм), запись этого алгоритма на одном из языков программирования становится элементом культуры многих работников из разных областей, в частности в экономике, которая тесно переплетается с математикой. Учащимся вполне доступно применение метода линейного программирования для нахождения максимума и минимума линейной функции от нескольких переменных при заданных дополнительно ограничениях для этих переменных. Изучение данного метода целесообразно начать с рассмотрения конкретных задач. Полезно дать задание написать рефераты по данной теме, рекомендовав работы академика Канторовича Л.В. «Математические методы организации и планирования производства», «Экономический расчет наилучшего использования ресурсов» и т. д., который стоял у истоков этого направления. Необходимо повторить способы решения систем линейных уравнений и неравенств. Предлагаемые задачи помогут составить представление о широте применения методов линейного программирования. Задачи 1 .С совхозного поля на овощную базу перевозятся овощи автомашинами грузоподъемностью по 5 и 10 тонн. За 1 час база может принять не более 10 машин, при этом не более 8 машин по 5 тонн и не более 6 машин по 10 тонн. Сколько машин по 5 и по 10 тонн нужно отправлять с поля на базу за 1 час, чтобы перевозить наибольшее количество овощей? Решение: Пусть за один час отправляется х машин по 5 тонн и у машин по 10 тонн. По условию задачи получим систему неравенств Всего за 1ч перевозится 5х + 10у тонн овощей. Задача свелась к нахождению наибольшего значения линейной функции S(х;у) = 5х + 10у в области, заданной системой неравенств. Множеством решений данной системы является многоугольник F, изображенный на рисунке. Среди всех точек многоугольника F функция S(х;у) = 5х + 10у принимает наибольшее значение в вершине многоугольника (4;6). Это значение равно S(4;6) = 5× 4 = 10× 6 = 80 Ответ: 4 машины по 5 т и 6 машин по 10 т. 2. Для откорма животных на ферме в их ежедневный рацион необходимо включать не менее 33 единиц питательного вещества А, 23 единицы питательного вещества В и 12 единиц питательного вещества С. Для откорма используются три вида кормов. Данные о содержании питательных веществ и стоимость одной весовой единицы каждого из кормов помещены в таблице
Составить наиболее дешевый рацион, при котором каждое животное получало бы необходимые количества питательных веществ А, В и С. Решение: Обозначим через х1, х2 и х3 количества кормов 1, 2 и 3 видов соответственно, включаемых в ежедневный рацион. Тогда каждое животное получит 4 х1 + 3х2 +2х3 единиц питательного вещества А, и это не должно быть меньше 33, т.е. 4 х1 + 3х2 +2х3 ³ 33. Для веществ В и С имеем: 3х1 + 2х2 +х3 ³ 23, х1 +х2 + 2х3 ³ 12. При таком расходовании кормов стоимость еженедельного рациона Z = 20х1 + 20х2 + 10х3. Учитывая, что по смыслу задачи х1 ³ 0, х2 ³ 0, х3 ³ 0, решение задачи сводится к определению наименьшего (минимального) значения линейной функции трех переменных Z = 20х1 + 20х2 + 10х3 при условии, что ее переменные х1, х2 и х3 должны удовлетворять системе неравенств: 4 х1 + 3х2 +2х3 ³ 33. 3х1 + 2х2 +х3 ³ 23, х1 +х2 + 2х3 ³ 12. х1 ³ 0, х2 ³ 0, х3 ³ 0. Решим систему способом подстановки. Из первого уравнения выразим неизвестную х1 через х2, х3 и свободный член d1: Исключая х1 из второго и третьего уравнений, получим систему или, после приведения подобных членов, (2) Из второго уравнения полученной системы (2) выразим неизвестную х2 через неизвестную х3 и свободные члены d1 и d2: х2= 3d1 – 4d1 – 2х3 и исключим ее из первого и третьего уравнений системы (2): Раскрыв скобки и приведя подобные члены, получим (3). Наконец, из третьего уравнения системы (3) определим неизвестную х3 : х3 = -d1 + d2 + d3, и исключим ее из первых двух уравнений системы (3): после упрощения получим: (4) в которой неизвестные х1, х2, х3 выражены через d1 ,d2, d3. Система (4) является решением поставленной задачи. Она и есть расчетная формула, по которой определяется еженедельный расход кормов. Например, если в еженедельный рацион животного должен входить 33 единицы питательного вещества А, 23 единицы питательного вещества В и 12 единиц питательного вещества С, то расход кормов распределяется следующим образом: Корм №1: х1 = -3.33+4. 23 + 12 =5 (весовых единиц) Корм №2: х2 = 5. 33 – 6 . 23 – 2. 12 =3 (весовые единицы) Корм №3: х3 = -33 + 23= 12 = 2 (весовые единицы) Задачи для самостоятельного решения 1. Рацион в нашем подсобном хозяйстве составляется из двух видов кормов – сена и концентратов. В таблице приведены данные о себестоимости кормов в хозяйстве (суточная потребность кормов на 1 корову равна 20 кормовых единиц).
Найти самый дешевый рацион, если ежедневный рацион кормления коров должен включать 16 кг сена. 2. Подсобному хозяйству выделено для возделывания кормовых культур 100 га пашни. Эту пашню предполагается занять пшеницей и картофелем, причем картофелем решено занять не менее 40 га. Как должна быть распределена площадь пашни по культурам, чтобы получилось наибольшее число кормовых единиц? При этом должно быть учтено следующее: 1 ц пшеницы содержит 0,2 ц кормовых единиц, 1 ц картофеля – 1, 26 ц. кормовых единиц, на возделывание 1 га пшеничного поля необходимо затратить 38 человека-часов труда механизаторов и 15 человека-часов ручного труда, а на 1 га поля, занятого картофелем, соответственно 43 и 185 человеко-часов, ожидаемый урожай картофеля 500 ц с га, а пшеницы 200 ц с га, и, наконец, всего на возделывание кормовых культур можно затратить 4000 человека-часов труда механизаторов и 15000 человеко-часов ручного труда. Указание. Ограничения: х1 + х2 100, 38х1 + 43х2 4000, 15х1 = 185х2 15000, х2 40, х1 0. Целевая функция имеет вид: у = 500 0,2х1 + 200 0,26х2. 3. Со школьных полей А и В нужно развести сено на склады №1, №2, №3. На поле А весь груз можно погрузить на 8 машин, а на станции В – на 10 машин. Склады должны принять: №1 – 5 машин, №2 – 7 машин, №3 – 6 машин. Количество бензина (в литрах), которое расходует одна машина на пробег от поля до склада, задается таблицей:
4. Для бригады выделили два участка земли в 8 га и в 9 га под посевы пшеницы и овса. Средняя урожайность по участкам и культурам отражена в таблице: (в ц на га)
За 1 ц пшеницы получают 600 руб., за 1 ц овса 400 руб.. Сколько гектаров и на каких участках необходимо посадить каждую культуру, чтобы получить наибольшую сумму от реализации продукции, если по плану надо собрать не менее 150 ц пшеницы и 220 ц овса? 5. Для изготовления стенда в школе требуются три планки – одна размером 1,2 м и две по 1,5 м каждая. Для этой цели можно использовать имеющийся запас реек – 40 штук, длиной 5 м каждая, и 10 штук, длиной по 6,5 м каждая. Определить, как разрезать все эти рейки, чтобы получить наибольшее количество стендов. 6. В школе провели конкурс на лучший рисунок к празднику «Золотая осень» Организаторы праздника дали нам поручение:
Мы истратили все деньги и купили 3 коробки красок, 6 коробок карандашей, 9 альбомов. Все ли данные поручения мы выполнили? 7. Для застекления одного окна в нашей школе требуется 4 стекла: два стекла размером 53126 (см2), одно - 5353 (см2), и одно для форточки - 44´44 (см2). Для этой цели можно использовать имеющийся запас стекол: 50 штук размером 60´120 (см2), 70 штук размером 60´200 (см2) каждое. Определить, как разрезать все стекла, чтобы получить наибольшее количество комплектов для застекления окон.
Решение: обозначим через х и у длины соответственно одной деревянной и одной проволочной стены. Площадь спортплощадки равна 810 м2. Обозначим общую стоимость забора через С, тогда по условию задачи общая стоимость забора С = 2×2у + 5×2х, или С = 10х + 4у (1), а площадь спортплощадки S= ху. По условию задачи ху = 810 (2). Из (2) получим у = 810 : х (3). Подставляя значение у в (10 получим функцию С(х) = 10х + 3240 : х. Итак, наша задача сводится к отысканию минимального значения полученной функции. Его не трудно найти по правилу отыскания наибольшего и наименьшего значения функции. В точке х = 18 функция С(х) имеет свое наименьшее значение. Итак, размеры спортплощадки, обеспечивающие минимальные затраты средств, 18 и 45 м. |
Методические рекомендации для проведения интеллектуальной игры «Умники... Интеллектуальная игра рассчитана на учащихся 5 классов при изучении на уроках литературы темы «Сказки зарубежных писателей» | Данная программа является составной частью образовательной программы... Программа курса «Информационные технологии и основы рекламного дела» предлагается для учащихся 10-11-х классов. Она рассчитана на... | ||
Годовой отчёт о проделанной работе за 2013 год клуба пос. Шудаяг му «цкс» мого «Ухта» На базе школы №7-продолжили свою работу возрастные клубы по интересам: «Почемучки» для учащихся 1 классов; ««Егоза» для учащихся... | Учебному предмету «Искусство» для 8-9 классов Программа предназначена для основной школы и рассчитана на два года обучения в 8 9 классах (68 часов). Данная рабочая программа разработана... | ||
Рабочая программа по физической культуре для 5 9-х классов составлена... «Комплексной программы физического воспитания учащихся 1-11 классов» (2007 г.) авторов Ляха В. И. и Зданевича А. А программа рассчитана... | Протокол №1 от Р. Р. Гимаев Программа элективного курса «Учись писать грамотно. Трудные случаи орфографии и пунктуации» рассчитана на учащихся 9-х классов | ||
Программа кружка “Занимательная химия” рассчитана на учащихся 8-9... Целью кружка является формирование у учащихся глубокого и устойчивого интереса к миру веществ и химических превращений, приобретение... | Образовательная программа по искусству (9 класс) Программа предназначена для учащихся 9 классов и рассчитана на 34 часа (по 1 часу в неделю) | ||
Программа кружка “Занимательная химия” рассчитана на учащихся 8-9... Целью создания кружка является формирование у учащихся глубокого и устойчивого интереса к миру веществ и химических превращений,... | «Исследователи» рассчитана для учащихся 6 -7 классов Срок реализации – 1 год Муниципальное бюджетное общеобразовательное учреждение Пичаевская средняя общеобразовательная школа | ||
Авторская программа научно исследовательского общества «Исследователи природы» Программа рассчитана на учащихся 7 -8 классов, имеющих базовый уровень знаний по разделу биологии ботанике | Программа по формированию навыков безопасного поведения на дорогах... Программа предназначена для учащихся 6-10 классов и рассчитана на 1 год обучения | ||
Образовательная программа по обществознанию Муниципального общеобразовательного учреждения Программа рассчитана на учащихся с 6 по 11 классы, изучающих предмет на базовом уровне, на учащихся 10-11 классов, проявляющих повышенный... | Основные типы занятий: беседа, диспут, практикум, просмотр и обсуждение фильма Программа предназначена для учащихся 9-11 классов и рассчитана на три года, 30 часов (1 час в месяц) | ||
Программа работы с одарёнными детьми по литературному чтению в 4 классе Интеллектуальная игра рассчитана на учащихся 5 классов при изучении на уроках литературы темы «Сказки зарубежных писателей» | Учебник Лесоводство 8-9 класс С. М. Космовский Программа предназначена для учащихся 8,9,10 классов как внеурочные и внешкольные занятия по выбору в соответствии с индивидуальными... |