Научно-исследовательская работа "Применение метода линейного программирования для планирования производства"

[Введите текст]

Муниципальное бюджетное образовательное учреждение
Средняя общеобразовательная школа №2 города Кузнецка

Применение метода линейного программирования для планирования производства.

Ученица: Куркина А.М.
Учитель: Кадырева С.А.

г. Кузнецк 2018г.

Содержание:

1. Введение.

2. Общая задача линейного программирования.

3. Примеры задач:
   3.1. Задача №1.
   3.2. Задача №2.
   3.3. Задача №3.

4. Заключение.
   Литература.

В своей работе я рассматриваю важные для практической деятельности человека задачи. Они очень разнообразны по своему содержанию, форме и приёмам решения. Но, несмотря на это разнообразие, их объединяет одна особенность – поиск наиболее выгодного, экономного, производительного, в определённых отношениях, способа. Этот поиск кратко можно назвать поиском наилучшего, ведь человека особенно интересует наилучшее, и в этом ему помогает математика.

Методы исследования:

1. Постановка гипотезы.

2. Сбор дидактического материала.

3. Систематизация и анализ полученного материала.

4. Доказательство истинности гипотез.

Общая задача линейного программирования:

Прежде чем определить, что такое линейное программирование рассмотрим задачу, которая имеет большое значение, - это так называемая «транспортная задача». Рассмотрим типичный пример такой задачи.

ЗАДАЧА:

Заводы и снабжают углем, который добывается на пунктах , , .

Известно, что в первом из этих пунктов ( добывается тонн угля в месяц, во втором, тонн угля, а в третьем - тонн угля. Первый завод потребляет тонн угля в месяц, второй тонн. Уголь привозится от пункта добычи к заводам по железной дороге. Известна стоимость провозки тонны угля от каждого пункта отправления до каждого пункта назначения: перевозка тонны угля от пункта до пункта стоит рублей, от пункта до пункта стоит рублей и т.д., от пункта до пункта стоит рублей (таблица 1).

Требуется так спланировать перевозки от пунктов А_{1 ,} А_{2 ,} А₃ к пунктам В₁ , В₂, чтобы затраты на перевозку угля были наименьшими.

РЕШЕНИЕ:

Пусть х₁₁ - количество угля в тоннах, которое перевозится от пункта А₁ к пункту В₁; х₁₂ – количество угля, отправляемое из пункта А₁ , в пункт В₂ и т.д. (таблица 2).

Тогда, должны выполняться условия:

х₁₁ + х₁₂ ≤ а_{1 ,}

х₂₁ + х₂₂ ≤ а_{2 ,}

х₃₁ + х₃₂ ≤ а_{3 ,} (1)

х₁₁ + х₂₁ + х₃₁ = b_{1 ,}

х₁₂ + х₂₂ + х₃₂ = b_{2 .}

Общая стоимость перевозок C определяется по формуле:

C = c₁₁x₁₁ + c₁₂x₁₂ + … + c₃₂x₃₂ (2)

Задача сводится к следующему: Требуется найти такую систему чисел X₁₁, X_{12 ,} … X_32, удовлетворяющих неравенствам и уравнениям (1), для которых величина C, определяется по формуле (2), будет минимальной (наименьшей). Выбор таких чисел X₁₁, X_12, … X₃₂ определит программу перевозок. С другой стороны, для решения этой задачи требуется рассмотреть систему линейных неравенств и уравнений и найти наименьшее значение линейной функции (2).

В связи с этим и говорят, что данная задача есть задача линейного программирования. Линейное программирование - это математическая дисциплина, занимающаяся способами решения таких задач, в которых требуется найти числа так, чтобы они удовлетворяли какой-то данной системы линейных уравнений и неравенств и чтобы, кроме этого, некоторая данная линейная функция от этих чисел имела наименьшее (или наибольшее) значение.

Примеры задач:

Познакомившись с методом линейного программирования, я поставила цель: применить этот метод в конкретных условиях для решения задач производства. Данные для этих задач я брала на Молочном комбинате, в мастерской по изготовлению мебели.

ЗАДАЧА №1:

Мастерская изготавливает шкафы. Для каждого шкафа заготавливается набор досок. В каждый такой набор должны войти 7 досок длиной 1 метр и 2 доски длиной в 2 метра (и одинаковой ширины в 20 сантиметров). Мастерская приобрела 200 досок длиной 3,1 метр (и шириной в 20 сантиметров), которые намерена использовать для изготовления шкафов. Как распилить две доски, чтобы получить, возможно, большее число шкафов?

РЕШЕНИЕ:

Из каждой доски длиной 3,1 метр можно получить доски требуемых размеров двумя способами:

1. Распилить её на 2 доски: 1 метр и 2 метра.

2. Распилить её на 3 доски длиной 1 метр.

Пусть x и y число досок, распиленных соответственно первым и вторым способами, z – число шкафов. Всего получено x двухметровых досок и x+3y метровых.

Поэтому: (1)

(2)

Кроме того, (3)

(4)

Требуется найти максимум функции

(5)

Так , то получаем

(6)

Множество точек , удовлетворяющих условию (6) есть .

Из точек этого множества наибольшую ординату Z имеет точка B. Чтобы найти эту ординату, решим систему:

Но, так как по смыслу задачи целое число, то .

Это и будет наибольшее число шкафов, которые можно заготовить из данных досок. Для них потребуется 108 двухметровых досок, поэтому 108 досок придется распилить первым способом.
Распилив остальные 92 доски вторым способом, получим достаточное для всех шкафов число метровых досок. Для 54 шкафов потребуется 378 метровых досок (из них 108 получены ранее). Чтобы получить остальные 270 метровых досок, достаточно распилить (вторым способом) лишь 90 досок.

Задача №2:

На молочном комбинате для производства двух видов продукции: напитка «Снежок» и напитка «Кефир» – используется молоко, закваска и сахар. Эти компоненты имеются на комбинате в следующих количествах: молоко – 9 тонн, сахар - 0,35 тонн, закваска – 1,5 тонн. На производство 1 тонны напитка «Снежок» и 1 тонны «Кефира» необходимо:

Прибыль от продажи 1 тонны напитка «Снежок» составляет 3 тыс. рублей, прибыль от продажи «Кефира» составляет 2,5 тыс. рублей. Требуется спланировать работу комбината так, чтобы обеспечить наибольшую прибыль.

Решение:

Пусть произведено тонн напитка «Снежок»,

тонн напитка «Кефир».

Тогда на производство этой продукции затрачено:

тонн молока,

( тонн сахара,

тонн закваски.

По условию задачи должны выполняться неравенства

.

Кроме того, по смыслу и неотрицательны .

Прибыль от реализации произведенной продукции равна

Таким образом, требуется определить максимум функции S в области, определяемой неравенствами.

15

100

9

7

1,5

55

0

Эта область представляет собой пятиугольник с вершинами:

(0;0), (0;10), (4,5;6), (7;1), (7;0). Так как S – линейная функция, то для нахождения ее максимума достаточно взять наибольшее из значений этой функции в указанных точках.

Максимальное значение равно 28,5 и достигается оно в точке (4,5;6). Таким образом, следует выпустить 4,5 тонны напитка «Снежок» и 6 тонн «Кефира». При этом будет израсходовано 9 тонн молока, 0,35 тонн сахара, 1,5 тонн закваски.

От реализации полученной продукции будет получена прибыль, равная 28,5 тыс. руб.

Задача технического контроля:

В отделе технического контроля (ОТК) некоторой фирмы работают контролеры разрядов 1 и 2. Норма выработки ОТК за 8-часовой рабочий день составляет не менее 1800 изделий. Контролер разряда 1 проверяет 25 изделий в час, причём не ошибается в 98% случаев. Контролер разряда 2 проверяет 15 изделий в час; его точность составляет 95%.

Заработная плата контролера разряда 1 равна 40 рублей в час, контролер разряда 2 получает 30 рублей в час. При каждой ошибке контролера фирма несёт убыток в размере 20 рублей. Фирма может использовать 8 контролеров разряда 1 и 10 контролеров разряда 2. Руководство фирмы хочет определить оптимальный состав ОТК, при котором общие затраты на контроль будут минимальны.

Решение:

Пусть x и y обозначают количество контролеров разрядов 1 и 2 соответственно. Число контролеров каждого разряда ограничено, т.е. имеются следующие ограничения:

Ежедневно необходимо проверять не менее 1800 изделий. Поэтому выполняется неравенство:

При построении функции следует иметь в виду, что расходы фирмы, связанные с контролем, включают две составляющие:

1) Зарплату контролеров,

2) Убытки, вызванные ошибками контролеров.

Расходы на одного контролера разряда 1 составляют

Расходы на одного контролера разряда 2 равны

Следовательно, функция, выражающая ежедневные расходы на контроль, имеет вид

Кроме того:

В этой задаче требуется найти значения переменных x и y, удовлетворяющие всем ограничениям и обеспечивающие минимальное значение функции. В качестве первого шага решение следует определить все возможные неотрицательные значения переменных x и y, которые удовлетворяют ограничениям. Например, координаты точки x=8 и y=10 положительны и для этой точки выполняются все ограничения. Такая точка называется допустимым решением. Множество всех допустимых решений называется допустимой областью. В рассматриваемом примере оптимальное решение представляет собой допустимое минимальное решение функции 400x+360y.

Все допустимые решения лежат в первом квадрате, поскольку значения переменных неотрицательны. В силу ограничения все допустимые решения (x, y) задачи располагаются по одному сторону от прямой, описываемой уравнением . Нужную полуплоскость можно найти, проверив, удовлетворяет ли начало координат рассматриваемому ограничению.

Допустимая область (ΔАВС) заштрихована. Ясно, что в допустимой области содержится бесконечное число допустимых точек. Нужно найти допустимую точку с наименьшим значением Z.

Если заранее зафиксировать значение функции Z=400x+360y, то соответствующие ему точки будут лежать на некоторой прямой. Точка А представляет собой наилучшую допустимую точку, соответствующую наименьшему значению Z, равному 377,6. Следовательно, х=8, y=1,6 - оптимальное решение и Z=377,6 - оптимальное значение рассматриваемой задачи линейного программирования.

Таким образом, при оптимальном режиме работы ОТК необходимо использовать восемь контролеров разряда 1 и 1.6 контролеров разряда 2. Дробное значение y=1,6 соответствует использованию одного из контролеров разряда 2 в течение неполного рабочего дня. При недопустимости неполной загрузки контролеров дробное значение обычно округляют, получая приближенное оптимальное целочисленное решение х=8, y=2.

Заключение:

Я ограничилась рассмотрением лишь таких задач, в которых число неизвестных не велико: в этих задачах цепь сводилась к поиску минимума и максимума линейной функции от двух переменных. В настоящее время разработаны разнообразные методы, которые позволяют решать задачи линейного программирования с большим числом неизвестных. Если неизвестных много, то решение таких задач приводит обычно к выполнению большого числа арифметических действий и поэтому приходится пользоваться современными быстродействующими вычислительными машинами. Применение методов линейного программирования к решению народнохозяйственных задач позволяет сэкономить большие денежные средства.
Решение этих задач практического содержания помогло мне лучше понять метод линейного программирования и выработать рекомендации для эффективного решения экономических задач.

Литература:

1. Балк М. Б. и Балк Г.Д. Математика после уроков. Пособие для учителей. М., «Просвещение» , 1971 г.

2. Колмогоров А. Н., Абрамов А. М. Алгебра и начала анализа. Учебное пособие для 10 класса средней школы – 4-е издание. М., «Просвещение» 1983 г.

3. Ашманов С.А Линейное программирование. М., Наука 1981 г.

4. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.1. Общие задачи, Минск, Изд-во БГУ им. В.И. Ленина 1977 г.