Проект "Графический способ решения задач линейного программирования" Федорова А.С, ученица 11 класса. Научный руководитель Тирский А С

МБОУ Районная гимназия «Эврика» Проектная работа

« Графический метод решения задач линейного программирования»

Выполнила: ученица 11 кл Федорова Алина Научный руководитель: учитель математики Тирский А.С. г.Олекминск Содержание Аннотация ……………………………………………………............. Теоретические основы решения задач линейного программирования графическим …………………………………

Практическое применение графического метода

решения задач линейного программирования………………….

Заключение

Список литературы………………………………………………….

Аннотация

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

Гипотеза: математическими методами можно решать экономические задачи.

Цель работы: изучение графического метода решения задач линейного программирования и определение области его применения в решении экономических задач.

Задачи:

1) изучить основные понятия и определения линейного программирования;

2) изучить теоретические основы графического метода решения задач линейного программирования;

3) рассмотреть примеры решения задач линейного программирования графическим методом;

4) определить область применения графического метода решения задач линейного программирования;

5) рассмотреть примеры практического применения графического метода для решения экономических задач оптимизации.

Предмет исследования: графический метод решения задач линейного программирования.

Методы исследования: изучение теоретического материала и практическое решение задач.

Теоретические основы решения задач линейного программирования графическим методом

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

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

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

Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи и записывается в общем виде как:

при ограничениях:

где xj — неизвестные; aij, bi, cj — заданные постоянные величины. Все или некоторые уравнения системы ограничений могут быть записаны также в виде неравенств.

Множество всех решений системы ограничений образуют область допустимых значений (ОДР). Если все условия системы ограничений являются уравнениями, то такая задача линейного программирования (ЗЛП) называется канонической. Если же есть неравенства, то неканонической.

Для составления математической модели ЗЛП необходимо:

1) обозначить переменные;

2) составить целевую функцию исходя из цели задачи;

3) записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности.

Самыми распространенными методами решений ЗЛП является:

• Графический метод

• Симплексный метод

Теоретические основы графического метода решения

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

Графический метод применяется для задач линейного программирования с двумя переменными, когда ограничения выражены неравенствами.

Линии уровня:

Суть метода:

 

При ограничениях:  

1. Строится ОДР в О  (множество решений системы ограничений).

2. Строится вектор – градиент целевой функции  .

Он показывает направление наискорейшего роста функции по значению.

1. Строим одну линию уровня, то есть эта линия в которой значение целевой функции постоянно  . Эта линия в случае линейной целевой функции представляет собой прямую перпендикулярную вектору – градиента.

2. Придавая   различные значения получаем семейство параллельных линий уровня. И эту линию уровня будем передвигать параллельно ей в направлении вектора, если решаем задачу на максимум, и в противном направлении, если на минимум, до тех пор, пока не получим точку выхода из ОДР(если max) или точку входа(если min).

3. Полученная точка и дает экстремальное значение функции. Эту точку называют оптимумом или оптимальным планом.

4. Вычисляем экстремальное значение целевой функции.

Практическое применение графического метода решения задач

линейного программирования

Пример 1. Задача оптимального использования ресурсов.

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

Исходный продукт	Расход исходных продуктов на 1 кг мороженого		Запас, кг
	Сливочное	Шоколадное
Молоко	0,8	0,5	400
Наполнители	0,4	0,8	365

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженого 16 ден. ед., шоколадного мороженого 14 ден. ед. Требуется определить, какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?

Решение.

Введем обозначения:

— суточный объем выпуска сливочного мороженого, кг,

— суточный объем выпуска шоколадного мороженого, кг.

Составим математическую модель задачи. Целевая функция будет иметь вид:

при ограничениях:

Решим задачу графическим методом.

1. Рассмотрим первое неравенство системы ограничений.

(8/10)  + (5/10)  ≤ 400

Построим прямую: (8/10)  + 5/10   = 400

Пусть =0 = 5/10, = 400 = = 800

Пусть =0 = 8/10, = 400 = = 500

Найдены координаты двух точек (0, 800) и (500, 0). Соединяем их и получаем прямую (1).

1. Рассмотрим второе неравенство системы ограничений.

4/10 + 8/10 ≤ 365

Построим прямую: 4/10 + 8/10 = 365

Пусть =0 = 8/10 = 365 = = 1825/4.

Пусть =0 = 4/10 = 365 = = 1825/2.

Найдены координаты двух точек (0, 1825/4) и (1825/2, 0). Соединяем их и получаем прямую (2).

1. Рассмотрим третье неравенство системы ограничений.

- ≤ 100

Построим прямую: - = 100

Пусть =0 = - = 100 = = -100

Пусть =0 = = 100

Найдены координаты двух точек (0, -100) и (100, 0). Соединяем их и получаем прямую (3).

1. Рассмотрим четвертое неравенство системы ограничений.

≤ 350

Построим прямую: = 350

Данная прямая параллельна оси OX1 и проходит через точку (0, 350),

получаем прямую (4).

1. Находим общую область решений всех неравенств системы ограничений,

получаем ОДР.

1. Строим вектор {16; 14}, его координатами являются коэффициенты функции L. Линия уровня L имеет уравнение 16 + 14 = сonst.

2. Перемещаем линию уровня по направлению вектора . Точкой выхода линии уровня L из области допустимых решений является точка A. Функция L достигает наибольшего значения в точке A.

Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений:

Решая систему, получим координаты точки A(312,5; 300), в которой и будет оптимальное решение, т. е. = 312,5; = 300.

L (312,5;300)=16 14 ∙ 300 = 9200 ден. ед.

Следовательно, L max= 9200 ден. ед.

Ответ: Максимальный доход от реализации составит 9200 ден. ед. в сутки

при выпуске 312,5 кг сливочного и 300 кг шоколадного мороженого.

Пример 2 Задача оптимального выбора рациона питания.

На ферме имеются корма для животных двух видов KI и K2, содержащие

питательные вещества трех типов В1, В2, и В3. Содержание питательных

веществ в 1 кг корма каждого вида и норма потребления в день питательных

веществ каждого типа приведены в таблице.

Питательные вещества	Число единиц питательных веществ в 1 кг корма		Норма потребления питательных веществ в день
	3	1	9
	1	2	8
	1	6	12

С тоимость 1 кг корма K₁ равна 12 ден. ед., стоимость 1 кг корма K₂ равна 18 ден. ед.

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

Решение:

Введем обозначения:

X₁ — количество корма KI в день, кг,

X₂ — количество корма K2 в день, кг.

Составим математическую модель задачи. Целевая функция будет иметь вид:

при ограничениях:

Решим задачу графическим методом.

1) Рассмотрим первое неравенство системы ограничений.

3 x₁ + x₂ ≥ 9

Построим прямую: 3 x₁ + x₂ = 9

Пусть x₁ =0 = x₂ = 9

Пусть x₂ =0 = 3 x₁ = 9 = x₁ = 3

Найдены координаты двух точек (0, 9) и (3, 0). Соединяем их и получаем прямую (1).

2) Рассмотрим второе неравенство системы ограничений.

X₁ + 2 x₂ ≥ 8

Построим прямую: x₁ + 2 x₂ = 8

Пусть x₁ =0 = 2 x₁ = 8 = x₂ = 4

Пусть x₂ =0 = x₁ = 8

Найдены координаты двух точек (0, 4) и (8, 0). Соединяем их и получаем прямую (2).

3) Рассмотрим неравенство 3 системы ограничений.

X₁ + 6 x₂ ≥ 12

Построим прямую: x₁ + 6 x₂ = 12

Пусть x₁ =0 = 6 x₂ = 12 = x₂ = 2

Пусть x₂ =0 = x₁ = 12

Найдены координаты двух точек (0, 2) и (12, 0). Соединяем их и получаем прямую (3).

4) Находим общую область решений всех неравенств системы ограничений,

получаем ОДР.

5) Строим вектор {12; 18}, его координатами являются коэффициенты

функции L. Линия уровня L имеет уравнение 12x₁ + 18x₂ = сonst.

6) Перемещаем линию уровня по направлению вектора . Точкой входа линии уровня L в область допустимых решений является точка A. Функция L достигает наименьшего значения в точке A.

Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений:

Решая систему, получим координаты точки A(2; 3), в которой и будет оптимальное решение, т. е. x₁ = 2; x₂ = 3

L (A) = 12 ∙ 2 + 18 ∙ 3 = 78 ден. ед.

Следовательно, L min = 78 ден. ед.

Ответ. Минимальная стоимость дневного рациона питания животных

составит 78 ден. ед. в сутки при условии, что он будет включать 2 кг корма K₁ и 3 кг корма K₁.

ЗАКЛЮЧЕНИЕ:

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

Графический метод используется для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции. Задачи линейной оптимизации решаются графическим методом в два этапа: построение области допустимых решений и нахождение в ее пределах оптимального решения.

Достоинствами графического метода являются: наглядность, простота

алгоритма решения и отсутствие большой трудоемкости вычислений.

Основным его недостатком является ограниченность применения, так как

решения задач выполняются на плоскости, что определяет число возможных

переменных, их не может быть более двух.

Прикладные задачи, связанные с отысканием оптимума заданной целевой функции при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.

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

Знания, приобретенные в процессе выполнения работы актуальны, и будут

мной использованы для продолжения образования в ВУЗе, а также в будущей профессиональной деятельности.