«Графический метод решения задачи линейного программирования»
ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МОРСКОГО И РЕЧНОГО ФЛОТА
имени адмирала С.О. МАКАРОВА
ИНСТИТУТ ВОДНОГО ТРАНСПОРТА
КАФЕДРАМАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ И ПРИКЛАДНОЙ ИНФОРМАТИКИ
УТВЕРЖДАЮ
Заведующий кафедрой
д.т.н., доцент
31. августа 2020г.
С.В. Колесниченко
Л Е К Ц И Я №3
ТЕМА: ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
НАПРАВЛЕНИЕ
ПОДГОТОВКИ:
09.03.03. ПРИКЛАДНАЯ ИНФОРМАТИКА
УЧЕБНАЯ
ДИСЦИПЛИНА:
Б1.О.21 ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И МЕТОДЫ
ОПТИМИЗАЦИИ
Обсуждена
на заседании кафедры
Протокол № 01 от 31 августа 2020
Разработал:
Профессор кафедры, к.в.н., доцент А.А. БУРЫКИН
Санкт-Петербург 2020
УДК 519.876.3
ББК 22.18
Рецензент:
Земсков А.В. доктор технических наук, профессор ГУМРФ имени адмирала С.О. Макарова
Бурыкин А.А., Графический метод решения задачи линейного программирования: Фондовая лекция по дисциплине «Исследование операций и методы оптимизации».
![](/800/600/http/cf.ppt-online.org/files/slide/s/SHiNJ8kxhpgKCvM6Pfc1w45eoRmYIZraU7tV29/slide-4.jpg)
![](/800/600/http/cf2.ppt-online.org/files2/slide/9/9QUBTOcAb1t4N2xr5Xw3lnSmkVgEsyaDpIKPFMv7f/slide-20.jpg)
![](/800/600/http/images.myshared.ru/5/357312/slide_8.jpg)
![](/800/600/http/images.myshared.ru/4/271844/slide_72.jpg)
![](/800/600/http/images.myshared.ru/4/92747/slide_3.jpg)
![](/800/600/http/otvet.imgsmail.ru/download/112081099_bce5d7d7db761b0964ca0dfb837b5e8b_800.png)
![](/800/600/http/prezentacii.org/upload/cloud/19/05/140826/images/screen9.jpg)
![](/800/600/http/privetstudent.com/uploads/posts/2013-03/1363886464_slayd66.jpg)
![](/800/600/http/images.myshared.ru/17/1105401/slide_15.jpg)
![](/800/600/http/otvet.imgsmail.ru/download/875a8375f91de049494d6073098e8a2f_1383b6237bad4b24e56afbe04fdaff99.jpg)
![](/800/600/http/cf.ppt-online.org/files1/slide/1/1QqilpZkF2jIBAouJ6GKsN0UnRfCYWcSdOxm8XHyP/slide-37.jpg)
![](/800/600/http/cf4.ppt-online.org/files4/slide/k/KCzWTdQGagAmjURuOPEXnwDr1L5M04hl2bSsfe/slide-11.jpg)
![](/800/600/http/cf.ppt-online.org/files/slide/b/bSTYVhlwc1s0QPyZtNMqIH2JkvuLej8WKzpA4G/slide-14.jpg)
Проект «Графический способ решения задач линейного программирования» Федорова А.С, ученица 11 класса. Научный руководитель Тирский А С
МБОУ Районная гимназия «Эврика» Проектная работа
« Графический метод решения задач линейного программирования»
Выполнила: ученица 11 кл Федорова Алина Научный руководитель: учитель математики Тирский А.С. г.Олекминск Содержание Аннотация ………………………………………………………………. Теоретические основы решения задач линейного программирования графическим …………………………………
Практическое применение графического метода
решения задач линейного программирования………………….
Заключение
Список литературы………………………………………………….
Аннотация
Актуальность данного исследования заключается не только в приобретении новых математических знаний в процессе выполнении работы, но и в определенными компетенциями, позволяющими использовать математический аппарат для решения прикладных экономических задач.
Гипотеза: математическими методами можно решать экономические задачи.
Цель работы: изучение графического метода решения задач линейного программирования и определение области его применения в решении экономических задач.
Задачи:
1) изучить основные понятия и определения линейного программирования;
2) изучить теоретические основы графического метода решения задач линейного программирования;
3) рассмотреть примеры решения задач линейного программирования графическим методом;
4) определить область применения графического метода решения задач линейного программирования;
5) рассмотреть примеры практического применения графического метода для решения экономических задач оптимизации.
Предмет исследования: графический метод решения задач линейного программирования.
Методы исследования: изучение теоретического материала и практическое решение задач.
Теоретические основы решения задач линейного программирования графическим методом
Линейное программирование (ЛП) – раздел прикладной математики, в котором изучаются методы решения задач на нахождение экстремальных (наибольших и наименьших) значений некоторой линейной функции, на неизвестные которой наложены линейные ограничения, в виде уравнений, неравенств или их систем.
Линейная функция называется целевой функцией, а ограничения, которые представляют количественные соотношения между переменными, выражающие условия и требования экономической задачи и математически записываются в виде уравнений или неравенств, называются системой ограничений.
С помощью задач линейного программирования решается широкий круг вопросов планирования экономических процессов, где ставится цель поиска наилучшего решения. В качестве целевой функции могут рассматриваться, например, прибыль от реализации (должна быть максимальной) или издержки производства (должны быть минимальными).
Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи и записывается в общем виде как:
при ограничениях:
где xj — неизвестные; aij, bi, cj — заданные постоянные величины. Все или некоторые уравнения системы ограничений могут быть записаны также в виде неравенств.
Множество всех решений системы ограничений образуют область допустимых значений (ОДР). Если все условия системы ограничений являются уравнениями, то такая задача линейного программирования (ЗЛП) называется канонической. Если же есть неравенства, то неканонической.
Для составления математической модели ЗЛП необходимо:
1) обозначить переменные;
2) составить целевую функцию исходя из цели задачи;
3) записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности.
Самыми распространенными методами решений ЗЛП является:
Графический метод
Симплексный метод
Теоретические основы графического метода решения
задач линейного программирования
Графический метод применяется для задач линейного программирования с двумя переменными, когда ограничения выражены неравенствами.
Линии уровня:
Суть метода:
При ограничениях:
Строится ОДР в О (множество решений системы ограничений).
Строится вектор – градиент целевой функции .
Он показывает направление наискорейшего роста функции по значению.
Строим одну линию уровня, то есть эта линия в которой значение целевой функции постоянно . Эта линия в случае линейной целевой функции представляет собой прямую перпендикулярную вектору – градиента.
Придавая различные значения получаем семейство параллельных линий уровня. И эту линию уровня будем передвигать параллельно ей в направлении вектора, если решаем задачу на максимум, и в противном направлении, если на минимум, до тех пор, пока не получим точку выхода из ОДР(если max) или точку входа(если min).
Полученная точка и дает экстремальное значение функции. Эту точку называют оптимумом или оптимальным планом.
Вычисляем экстремальное значение целевой функции.
Практическое применение графического метода решения задач
линейного программирования
Пример 1. Задача оптимального использования ресурсов.
Фирма выпускает два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы исходных продуктов даны в таблице.
Исходный продукт | Расход исходных продуктов на 1 кг мороженого | Запас, кг | |
Сливочное | Шоколадное | ||
Молоко | 0,8 | 0,5 | 400 |
Наполнители | 0,4 | 0,8 | 365 |
Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженого 16 ден. ед., шоколадного мороженого 14 ден. ед. Требуется определить, какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?
Решение.
Введем обозначения:
— суточный объем выпуска сливочного мороженого, кг,
— суточный объем выпуска шоколадного мороженого, кг.
Составим математическую модель задачи. Целевая функция будет иметь вид:
при ограничениях:
Решим задачу графическим методом.
Рассмотрим первое неравенство системы ограничений.
(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).
Рассмотрим второе неравенство системы ограничений.
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).
Рассмотрим третье неравенство системы ограничений.
— ≤ 100
Построим прямую: — = 100
Пусть =0 = — = 100 = = -100
Пусть =0 = = 100
Найдены координаты двух точек (0, -100) и (100, 0). Соединяем их и получаем прямую (3).
Рассмотрим четвертое неравенство системы ограничений.
≤ 350
Построим прямую: = 350
Данная прямая параллельна оси OX1 и проходит через точку (0, 350),
получаем прямую (4).
Находим общую область решений всех неравенств системы ограничений,
получаем ОДР.
Строим вектор {16; 14}, его координатами являются коэффициенты функции L. Линия уровня L имеет уравнение 16 + 14 = сonst.
Перемещаем линию уровня по направлению вектора . Точкой выхода линии уровня 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 кг корма K1 равна 12 ден. ед., стоимость 1 кг корма K2 равна 18 ден. ед.
Необходимо составить дневной рацион питания животных, имеющий минимальную стоимость, и содержащий питательные вещества каждого типа не менее установленной нормы потребления.
Решение:
Введем обозначения:
X1 — количество корма KI в день, кг,
X2 — количество корма K2 в день, кг.
Составим математическую модель задачи. Целевая функция будет иметь вид:
при ограничениях:
Решим задачу графическим методом.
1) Рассмотрим первое неравенство системы ограничений.
3 x1 + x2 ≥ 9
Построим прямую: 3 x1 + x2 = 9
Пусть x1 =0 = x2 = 9
Пусть x2 =0 = 3 x1 = 9 = x1 = 3
Найдены координаты двух точек (0, 9) и (3, 0). Соединяем их и получаем прямую (1).
2) Рассмотрим второе неравенство системы ограничений.
X1 + 2 x2 ≥ 8
Построим прямую: x1 + 2 x2 = 8
Пусть x1 =0 = 2 x1 = 8 = x2 = 4
Пусть x2 =0 = x1 = 8
Найдены координаты двух точек (0, 4) и (8, 0). Соединяем их и получаем прямую (2).
3) Рассмотрим неравенство 3 системы ограничений.
X1 + 6 x2 ≥ 12
Построим прямую: x1 + 6 x2 = 12
Пусть x1 =0 = 6 x2 = 12 = x2 = 2
Пусть x2 =0 = x1 = 12
Найдены координаты двух точек (0, 2) и (12, 0). Соединяем их и получаем прямую (3).
4) Находим общую область решений всех неравенств системы ограничений,
получаем ОДР.
5) Строим вектор {12; 18}, его координатами являются коэффициенты
функции L. Линия уровня L имеет уравнение 12x1 + 18x2 = сonst.
6) Перемещаем линию уровня по направлению вектора . Точкой входа линии уровня L в область допустимых решений является точка A. Функция L достигает наименьшего значения в точке A.
Точка A одновременно принадлежит прямым (1) и (2). Составим систему уравнений:
Решая систему, получим координаты точки A(2; 3), в которой и будет оптимальное решение, т. е. x1 = 2; x2 = 3
L (A) = 12 ∙ 2 + 18 ∙ 3 = 78 ден. ед.
Следовательно, L min = 78 ден. ед.
Ответ. Минимальная стоимость дневного рациона питания животных
составит 78 ден. ед. в сутки при условии, что он будет включать 2 кг корма K1 и 3 кг корма K1.
ЗАКЛЮЧЕНИЕ:
Изучив теоретические основы графического метода решения задач линейного программирования, установив область его применения, а также оценив практические результаты применения графического метода для решения прикладных экономических задач, можно сделать следующие выводы:
Графический метод используется для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции. Задачи линейной оптимизации решаются графическим методом в два этапа: построение области допустимых решений и нахождение в ее пределах оптимального решения.
Достоинствами графического метода являются: наглядность, простота
алгоритма решения и отсутствие большой трудоемкости вычислений.
Основным его недостатком является ограниченность применения, так как
решения задач выполняются на плоскости, что определяет число возможных
переменных, их не может быть более двух.
Прикладные задачи, связанные с отысканием оптимума заданной целевой функции при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.
Графический метод используется для решения практических экономических задач оптимизации. В этом случае составляется математическая модель, где переменные – это некоторые экономические ресурсы, оптимальную величину которых необходимо найти для получения наилучшего результата экономической деятельности. Таким образом выдвинутая мной гипотеза нашла свое подтверждение.
Знания, приобретенные в процессе выполнения работы актуальны, и будут
мной использованы для продолжения образования в ВУЗе, а также в будущей профессиональной деятельности.
Z = x+y С учетом ограничений , 5x+10yle50,x+yge1,yle4,x,yge0.
![](/800/600/http/cf.ppt-online.org/files/slide/a/A9aPfpgKQSj64DbFEU0tYVqeyCsdXHnZORrLuk/slide-11.jpg)
UNITED BOOK HOUSE-ВОПРОСНИК 2017-УПРАЖНЕНИЕ
20 видеоРЕКЛАМА
Ab Padhai каро бина адс ке
Khareedo DN Про и дехо сари видео бина киси ад ки рукаават ке!
Ответить
Пошаговое решение, разработанное экспертами, чтобы помочь вам в решении вопросов и получении отличных оценок на экзаменах.
Похожие видео
Решите графически следующую задачу линейного программирования.
Минимизация :z=2x+3y−1
С учетом:
x−y≥0
−x+2y≥2
x≥3
y≤4
y≥0
31348158
Решите следующую задачу линейного программирования. Графически:
Максимизация: z = x+2y
с помощью: x -≤2
x+y≤4
x≥0
y≥0
31348177
Текстовый раствор
निम Как पана प wantra आलेखीय आलेखीय Как से करें।
z=3x+5y जबकि
2x+y≤4,
x+y≥03,
x -2y≤2,
x, y≥0
119393882
Текстовое решение
निम्नलिखित ैखिक प्रोग्रामन समस्या को आलेखीय से निम क क पраться
अधिकतमीकरण करें z = 3x+ry जबकि
x+y≤4, x≥0, y≥0
119393922
Решение следующей линейной задачи программирования в графическом методе, подверженных ограничениям, 5x+10yle50.
234809357
লেখচিত্রের সাহায্যে নীচের প্রোগ্রামবিধির সমস্যাটি সমাধান করো। Z=(x+y) -কে চরম করো,
নীচের শর্তাবলী সাপেক্ষে: 5x+10y≤50,
x+y≥1,
y≤4,
এবং x≥0,y≥0.
দেখাও যে সমস্যাটির একটি এক একক একক (уникальный) প্রান্তিক সমাধান (оптимальсулюция) আছে।
395312825
Решите графически следующую задачу линейного программирования:
Рассмотрим задачу линейного программирования:
Максимум z=50x+40y
с учетом ограничений:
x+2y≤10,3x+4y≥24,x,y≥0
Найдите максимальное значение z.
642941587
आलेखीय विधि द्वारा निम्न रैखिक प Вивра समस्या को हल कीजिए कीजिए कीजिए कीजिए निम समसtrत क अन्य को हल कीजिए कीजिए कीजिए कtr 25trगत क. |
643040638
निम्नलिखित में से किन्ही तीन खणхов खण को हल कीजिये
आलेखीय विधि द chven द y ≥ ≥ निम निम निम निमprैखिक ≥ निम निम निमpr+≥ निमчего निम निम निमpr+व निम निमpr+व निमраться. का अधिकतम मान ज्ञात कीजिये
643040663
Решите графически следующую задачу линейного программирования.
Минимизировать :z=2x+3y−1
С учетом:
x−y≥0
−x+2y≥2
x≥3
y≤4
y≥0
644856048
Решить следующую задачу линейного программирования графически:
Максимизировать :z=x+2y
С учетом: x−y≤2
x+y≤4
x≥0
y≥0
644856062
Максимизировать Z=3x+4y, с учетом ограничений x +y≤4,x≥0,y≥0
644871621
Решите графически следующую задачу линейного программирования
Максимум Z=60x+15y
С учетом ограничений x+y≤30,3x+y≤90 и x,y≥0.
644961751
Графически решить задачу линейного программирования: Минимизировать Z=2x+y при условии 5x+10yle50,x+yge1,yle4 , x,yge0
645096689
[Решено] Графически решить следующую задачу линейного программирования: …
Вопрос задан ProfessorSheepMaster381 на сайте coursehero.com
Решите графически следующую задачу линейного программирования:
Максимизируйте z = 500×1 + 400×2
с подлежит:
10×1 + 20×2 ≤ 100
5×1 + 10×2 ≤ 50
4×1 — 2×2 ≤ 100003
≤ x1 + 2×2 ≤ 15 9000 2
rt. 0
Вопросы:
- Нарисуйте ограничения (не забудьте четко обозначить их, чтобы указать, какая линия соответствует какому ограничению) и определите достижимую область (затените/затемните достижимую область). Предоставьте все необходимые шаги/расчеты для обоснования ваших ответов.
- Нарисуйте целевую функцию, затем определите оптимальное решение(я) и максимальное значение целевой функции. Предоставьте все необходимые шаги/расчеты для обоснования ваших ответов.
- Какой другой метод можно выбрать для поиска оптимального решения без построения целевой функции? Учитывая структуру допустимой области, какой метод лучше? Обосновать ответ.
БизнесБизнес — Другое
Ответил manolinoericka на сайте coursehero.com
sectetur adipiscing elit. Nam lacinia pulvinar tortor nec facilisis. Pellentesque dapibus efficitur laoreet. Nam risus ante, dapibus a molestie consequat, ultrices ac magna. Fusce dui lectus, congue vel laoreet ac, dictum vitae odio. Донец Аликет. Lorem ipsum
Разблокировать доступ к этому и через
10 000 пошаговых объяснений
Есть учетная запись? Войти
sectetur adipiscing elit. Nam lacinia pulvinar tortor nec facilisis. Pellentesque dapibus efficitur laoreet. Nam risus ante, dapibus a molestie consequat, ultrices ac magna. Fusce dui lectus, congue vel laoreet ac, dictum vitae odio. Донец Аликет. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nam lacinia pulvinar tortor nec facilisis. Pellentesque dapibus efficitur laoreet. Nam risus ante, dapibus a molestie consequat, ultrices ac magna. Fusce dui lectus, congue vel laoreet ac, dictum vitae odio. Донец Аликет. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nam lacinia pulvinar tortor nec facilisis. Pellentesque dapibus efficitur laoreet. Nam risus ante, dapibus a molestie consequat, ultrices ac magna. Fusce dui lectus, congue vel laoreet ac, dictum vitae odio. Донец Аликет. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nam lacinia pulvinar tortor nec facilisis. Pellentesque dapibus efficitur laoreet. Nam risus ante, dapibus a molestie consequat, ultrices ac magna. Fusce dui lectus, congue vel laoreet ac, dictum vitae odio. Донец Аликет. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nam lacinia pulvinar tortor nec facilisis. Pellentesque dapibus efficitur laoreet. Nam risus ante, dapibus a molestie consequat, ultrices ac magna. Fusce dui lectus, congue vel laoreet ac, dictum vitae odio. Донец Аликет. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nam lacinia pulvinar tortor nec facilisis. Pellentesque dapibus efficitur laoreet. Nam risus ante, dapibus a molestie consequat, ultrices ac magna. Fusce dui lectus, congue vel laoreet ac, dictum vitae odio. Донец Аликет. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nam lacinia pulvinar tortor nec facilisis.