Файл: Сущность математического программирования 5 1 Линейное программирование 5.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.05.2024
Просмотров: 31
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Методика решения задач ЛП графическим методом.
В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.
Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .
Пример: Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем
, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.
Переменные задачи
В задаче требуется установить, сколько радиоприемников первой и второй модели надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого типа радиоприемников:
– суточный объем производства радиоприемников первой модели, [шт/сутки];
– суточный объем производства радиоприемников второй модели, [шт/сутки];
Целевая функция
Цель задачи – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи радиоприемников обоих моделей, необходимо знать:
- их объемы производства, т.е. и радиоприемников в сутки;
- прибыль от их реализации – согласно условию, соответственно 40 и 20 $.
Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен $ в сутки, а от продажи радиоприемников второй модели – $ в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:
[$/сутки]
Возможные объемы производства радиоприемников и ограничиваются следующими условиями:
- количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;
- суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) – 80 шт;
- объемы производства радиоприемников не могут быть отрицательными.
Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:
1) расходом элементов электронных схем;
2) суточным объемом технологических линий;
3) неотрицательностью объемов производства.
Запишем эти ограничения в математической форме:
Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид: [шт/сутки]
Ограничения по суточному объему первой и второй технологических линий имеют вид: [шт/сутки]
Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.3.1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.
Точки пересечения с осями – (0;75) и (37,5;0)
Строим вектор из точки (0;0) в точку (40;20). Точка D – это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D – это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)
Получили точку D(60;5) [шт/сутки].
Максимальное значение ЦФ равно [$/сутки].
Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит 2500$ в сутки.11
ЗАКЛЮЧЕНИЕ
В данной курсовой работе мною были освоены навыки решения задач линейного программирования геометрическим методом. Для этого я изучила теоретические сведения, необходимые для решения задач линейного программирования указанным методом. Я узнала, что данный метод применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно. Также я узнала, как строятся прямые на плоскости, для чего разобрала основные понятия линейной алгебры и выпуклого анализа. После чего, рассмотрела все этапы геометрического решения задач линейного программирования, благодаря чему я узнала, что бывают разные случаи при решении задач, а именно:
-
Основной случай, когда полученная область образует ограниченный выпуклый многоугольник; -
Неосновной случай, когда полученная область образует неограниченный выпуклый многоугольник; -
И также, возможен случай, когда неравенства противоречат друг другу, и допустимая область пуста, то есть данная задача не будет иметь решений.
В первых двух случаях задача может иметь единственное решение в конкретной точке, а также в любой точке отрезка или луча.
Таким образом, освоив все необходимые навыки использования геометрического метода для решения задач линейного программирования, я решила поставленные задачи.
СПИСОК ЛИТЕРАТУРЫ
-
А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М. 2000 г.. -
Алабин Б.К. «Методы исследования операций» (курс лекций). -
Бессмертный, И. А. Системы искусственного интеллекта : учеб. пособие для СПО / И. А. Бессмертный. — 2-е изд., испр. и доп. — М. : Издательство Юрайт, 2018. — 130 с. -
Воротницкий Ю.И. «Исследование операций». -
Гниденко, И. Г. Технология разработки программного обеспечения : учеб. пособие для СПО / И. Г. Гниденко, Ф. Ф. Павлов, Д. Ю. Федоров. — М. : Издательство Юрайт, 2017. — 235 с. -
Гордеев, С. И. Организация баз данных в 2 ч. Часть 2 : учебник для вузов / С. И. Гордеев, В. Н. Волошина. — 2-е изд., испр. и доп. — М. : Издательство Юрайт, 2019. — 501 с. -
Давыдов Э.Г. «Исследование операций», 1990 г.. -
Дегтярев Ю.И. «Исследование операций», 1986 г.. -
Жмудь, В. А. Моделирование замкнутых систем автоматического управления : учеб. пособие для академического бакалавриата / В. А. Жмудь. — 2-е изд., испр. и доп. — М. : Издательство Юрайт, 2019. — 128 с. -
Зыков, С. В. Программирование. Объектно-ориентированный подход : учебник и практикум для академического бакалавриата / С. В. Зыков. — М. : Издательство Юрайт, 2019. — 155 с. -
Иванов, В. М. Интеллектуальные системы : учеб. пособие для вузов / В. М. Иванов ; под науч. ред. А. Н. Сесекина. — М. : Издательство Юрайт, 2017. — 91 с. -
Иванов, В. М. Интеллектуальные системы : учеб. пособие для СПО / В. М. Иванов ; под науч. ред. А. Н. Сесекина. — М. : Издательство Юрайт, 2019. — 93 с. -
Коротков М., Гаврилов М. «Основы линейного программирования», 2003 г.. -
Кубенский, А. А. Функциональное программирование : учебник и практикум для академического бакалавриата / А. А. Кубенский. — М. : Издательство Юрайт, 2019. — 348 с. -
Кудрина, Е. В. Основы алгоритмизации и программирования на языке c# : учеб. пособие для СПО / Е. В. Кудрина, М. В. Огнева. — М. : Издательство Юрайт, 2019. — 322 с. -
Кудрина, Е. В. Основы алгоритмизации и программирования на языке c# : учеб. пособие для бакалавриата и специалитета / Е. В. Кудрина, М. В. Огнева. — М. : Издательство Юрайт, 2019. — 322 с. -
Кудрявцев, К. Я. Методы оптимизации : учеб. пособие для вузов / К. Я. Кудрявцев, А. М. Прудников. — 2-е изд. — М. : Издательство Юрайт, 2019. — 140 с. -
Лаврищева, Е. М. Программная инженерия и технологии программирования сложных систем : учебник для вузов / Е. М. Лаврищева. — 2-е изд., испр. и доп. — М. : Издательство Юрайт, 2019. — 432 с. -
Лебедев, В. М. Программирование на vba в ms excel : учеб. пособие для академического бакалавриата / В. М. Лебедев. — М. : Издательство Юрайт, 2019. — 272 с. -
Лищенко «Линейное и нелинейное программирование», М. 2003 г.. -
Малявко, А. А. Формальные языки и компиляторы : учеб. пособие для вузов / А. А. Малявко. — М. : Издательство Юрайт, 2018. — 429 с -
Мамонова, Т. Е. Информационные технологии. Лабораторный практикум : учеб. пособие для СПО / Т. Е. Мамонова. — М. : Издательство Юрайт, 2019. — 178 с. -
Маркин, А. В. Программирование на sql в 2 ч. Часть 2 : учебник и практикум для бакалавриата и магистратуры / А. В. Маркин. — М. : Издательство Юрайт, 2019. — 292 с. -
Мину М. Математическое программирование. Теория и алгоритмы. М. 2004 г.. -
Нагаева, И. А. Программирование: delphi : учеб. пособие для академического бакалавриата / И. А. Нагаева, И. А. Кузнецов ; под ред. И. А. Нагаевой. — М. : Издательство Юрайт, 2017. — 302 с. -
Плескунов, М. А. Операционное исчисление : учеб. пособие для вузов / М. А. Плескунов ; под науч. ред. А. И. Короткого. — М. : Издательство Юрайт, 2019. — 141 с. -
Советов, Б. Я. Базы данных : учебник для прикладного бакалавриата / Б. Я. Советов, В. В. Цехановский, В. Д. Чертовской. — 3-е изд., перераб. и доп. — М. : Издательство Юрайт, 2019. — 420 с. -
Стасышин, В. М. Базы данных: технологии доступа : учеб. пособие для СПО / В. М. Стасышин, Т. Л. Стасышина. — 2-е изд., испр. и доп. — М. : Издательство Юрайт, 2018. — 164 с. -
Теха Х. «Введение в исследование операций», Издательский дом «Вильямс», 2001 г.. -
Филькин Г.В., «Линейное программирование» (лекции), Шахты, 2007 г..
1 А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М. 2000 г..
2 Гордеев, С. И. Организация баз данных в 2 ч. Часть 2 : учебник для вузов / С. И. Гордеев, В. Н. Волошина. — 2-е изд., испр. и доп. — М. : Издательство Юрайт, 2019. — 501 с.
3 Мамонова, Т. Е. Информационные технологии. Лабораторный практикум : учеб. пособие для СПО / Т. Е. Мамонова. — М. : Издательство Юрайт, 2019. — 178 с.
4 Кудрявцев, К. Я. Методы оптимизации : учеб. пособие для вузов / К. Я. Кудрявцев, А. М. Прудников. — 2-е изд. — М. : Издательство Юрайт, 2019. — 140 с.
5 Бессмертный, И. А. Системы искусственного интеллекта : учеб. пособие для СПО / И. А. Бессмертный. — 2-е изд., испр. и доп. — М. : Издательство Юрайт, 2018. — 130 с.
6 Гниденко, И. Г. Технология разработки программного обеспечения : учеб. пособие для СПО / И. Г. Гниденко, Ф. Ф. Павлов, Д. Ю. Федоров. — М. : Издательство Юрайт, 2017. — 235 с.
7 Иванов, В. М. Интеллектуальные системы : учеб. пособие для вузов / В. М. Иванов ; под науч. ред. А. Н. Сесекина. — М. : Издательство Юрайт, 2017. — 91 с.
8 Алабин Б.К. «Методы исследования операций» (курс лекций).
9 Воротницкий Ю.И. «Исследование операций».
10 Зыков, С. В. Программирование. Объектно-ориентированный подход : учебник и практикум для академического бакалавриата / С. В. Зыков. — М. : Издательство Юрайт, 2019. — 155 с.
11 Лаврищева, Е. М. Программная инженерия и технологии программирования сложных систем : учебник для вузов / Е. М. Лаврищева. — 2-е изд., испр. и доп. — М. : Издательство Юрайт, 2019. — 432 с.