Invest-currency.ru

Как обезопасить себя в кризис?
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

ПОНЯТИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ВИДЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

Линейное программирование применяется при решении следующих экономических задач:

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

2. Задач определения оптимального размещения оборудования на морских судах, в цехах.

3. Задача определения оптимального плана перевозок груза (транспортная задача).

4. Задача оптимального распределения кадров.

5. Задач о смесях, диете (планирование состава продукции) и т.д.

3. МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЁ ПРЕДСТАВЛЕНИЕ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ MS EXCEL.

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

Основные этапы создания модели линейного программирования в Excel:

1. Написание и проверка символической модели линейного программирования. Модель записывается на бумаге в математическом виде.

2. Создание и отладка табличной модели линейного программирования. На основе символической модели ЛП создается ее представление в Excel.

3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.

4. ИСПОЛЬЗОВАНИЕ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ.

С помощью электронных таблиц можно моделировать реальные ситуации и оценивать полученные результаты. Другими словами с помощью электронных таблиц можно делать анализ результатов деятельности и прогнозирования будущих перспектив предприятия. Эти задачи в среде MS Excel дает возможность решать надстройка Поиск решения.

Поиск решения – это надстройка, которая предназначена для оптимизации моделей при наличии ограничений. Она состоит из двух программных компонентов: программы написанной на языке Visual Basic, который транслирует представленную на рабочем письме информацию для внутреннего представления, которая используется другой программой. Вторая программа находится в памяти компьютера в виде отдельного программного модуля. Она выполняет оптимизацию и возвращает найденное решение первой программе, которая возобновляет данные на рабочем листе. С помощью ее можно найти оптимальное значение формулы, которая сохраняется в целевой ячейке. Эта процедура работает с группой ячеек, которые непосредственно связанные с формулой в целевой ячейке. Чтобы получить результат по формуле в целевой ячейке, процедура изменяет значение в ячейках, которые влияют на поиск. Для того, чтобы уменьшить множественное число значений, которые используются в модели задачи, применяют ограничение. Эти ограничения могут содержать ссылку на другие ячейки, которые влияют на поиск.

Общий алгоритм работы с надстройкой Поиск решения.

  1. В меню Сервис выбрать команду Поиск решения.
  2. В поле Установит целевую ячейку введите адрес ячейки, в которй находится формула, для оптимизации модели.
  3. Для того, чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Максимальному значению. Для того, чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Минимальному значению. Для того, чтобы целевая ячейка приобретала значение конкретного числа, установите переключатель в положение Значение и введите соответствующее число.
  4. В поле Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Изменяемые ячейки должны быть прямо или непрямо связанные с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
  5. В поле Ограничения введите все ограничения, которые налагаются на поиск решения.
  6. Нажмите кнопку Выполнить.
  7. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение. Для возобновления входных данных установите переключатель в положение Восстановить исходные значения.
  8. Для того, чтобы прервать поиск решения, нажмите клавишу Еsс. MS Excel пересчитает лист с учетом найденных значений ячеек, которые влияют на результат.

Алгоритм роботи з надбудовою Поиск решения.

5. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩИ ПРОГРАММЫ MS EXCEL.

Пример. Кондитерский цех для изготовления трех видов карамели А, В, С использует три основных вида сырья: сахар, патоку и фруктовое пюре. Нормы затрат сахара на изготовление 1кг карамели каждого вида соответственно уровни: 0,8кг; 0,5кг; 0,6кг; патоки – 04кг; 0,4кг; 0,3кг; фруктового пюре – 0кг; 0,1кг; 0,1кг. Конфеты можно производить в любых количествах (реализация обеспечена), но запас сырья ограниченный: запасы сахара – 80кг, патоки – 60кг, фруктового пюре – 12кг. Прибыль от реализации 1кг карамели вида А составляет 10грн., вида В – 11грн., вида С – 12грн.

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

: Задачи линейного программирования (ЗЛП)

1. Линейное программирование

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

3. Формы записи ЗЛП

4. Каноническая форма задач линейного программирования

Линейное программирование

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

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

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

Рисунок 1 — Экстремум целевой функции

Математическая модель ЗЛП записывается следующим образом:

max (или min) Z=z(X),(1)

ОДР может быть представлена системой линейных уравнений или неравенств.

Вектор Х=(х1, х2, . xп) является вектором управления или управляющим воздействия.

Допустимый план Х, при котором критерий оптимальности Z=z(X) достигает экстремального значения, называется оптимальным и обозначается через X*, экстремальное значение целевой функции — через Z*=z(X*).

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

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

Наиболее распространенный тип задач — задача оптимального использования ресурсов. Пусть некоторая производственная единица (цех, предприятие, объединение и т.д.), исходя из конъюнктуры рынка, технических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции, известных под номерами j.

При выпуске продукции предприятие ограничено имеющимися ресурсами, количество которых обозначим m, а вектор ресурсов В = (b1, b2, . bт). Известны также технологические коэффициенты aij, которые показывают норму расхода i-го ресурса на производство единицы j-ой продукции. Эффективность выпуска единицы j-и продукции характеризуется прибылью pj.

Требуется определить план выпуска продукции Х=(х1, х2, . xп), максимизирующий прибыль предприятия при заданных ресурсах.

Целевая функция выглядит следующим образом

Часто ассортимент продукции устанавливается вышестоящей организацией, т. е. его объемы должны быть заключены в некоторых границах D н j и D в j:тогда задается следующее ограничение:

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

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

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

1) максимум прибыли

2) минимум затрат на производство

3) максимум выпуска в стоимостном выражении (выручки от реализации продукции)

Пример. Предприятие может изготовлять четыре вида продукции 1, 2, 3 и 4. Сбыт любого ее объема обеспечен. Предприятие располагает в течение квартала трудовыми ресурсами в 100 человеко-смен, полуфабрикатами массой 260 кг, станочным оборудованием в 370 станко-смен. Нормы расхода ресурсов и прибыль от единицы каждого вида продукции представлены в табл.1.

а) составить математическую модель задачи определения плана выпуска продукции, при котором достигается максимум прибыли;

б) решить задачу с требованием комплектации, чтобы количество единиц третьей продукции было в 3 раза больше количества единиц первой;

в) выяснить оптимальный ассортимент при дополнительных условиях: первого продукта выпускать не менее 25 единиц, третьего — не более 30, а второго и четвертого — в отношении 1:3.

Трудовые ресурсы, человеко-смен

Станочное оборудование, станко-смен

Прибыль от единицы продукции, руб.

Математическая модель задачи:

а) на трудовые ресурсы:

на станочное оборудование:

б) дополнительное требование комплектации выразится условием

в) граничные условия и условие комплектации представим так: х1?25,

Задача о размещении заказов или загрузке взаимозаменяемых групп оборудования. Речь идет о распределения заказов между m (i=1,…, m) предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказов. Требуется составить такой план размещения заказов, при котором задание было бы выполнено, а показатель эффективности достигал экстремального значения.

Сформулируем задачу математически. Пусть на т однородных группах оборудования нужно изготовить п видов продукции. План выпуска каждого вида продукции на определенный период задан набором хj (j=1,2, …п). Мощность каждого вида оборудования ограничена и равна bi. Известна технологическая матрица A=||aij||, где aij—число единиц j-ой продукции, выпускаемой в единицу времени на i-м оборудовании. Матрица С — матрица затрат, где cij—затраты, связанные с выпуском единицы j-й продукции на i-м оборудовании. Х — вектор объема выпускаемой продукции.

Модель задачи примет следующий вид:

целевая функция — минимизация расходов на реализацию всех заказов

а) по мощности оборудования

б) на выпуск продукции

в) условие неотрицательности

Данную задачу называют распределительной или задачей распределения.

Если по некоторым видам продукции допускается превышение плана, то ограничение (б) примет вид

В качестве целевой прибыли также можно принять:

а) максимум прибыли

б) минимум затрат станочного времени

Т.к. любая модель содержит упрощающие предпосылки, для корректного применения полученных результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее существенным упрощением в рассмотренных моделях является предположение о прямопропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат aij. Очевидно, что это допущение далеко не всегда выполняется. Так объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно — в зависимости от изменения программы производства Х. К другим упрощающим предпосылкам относятся предположения о независимости цен j от объемов xj, что справедливо лишь для определенных пределов их изменения. Данные «уязвимые» места важно знать еще и потому, что они указывают принципиальные направления усовершенствования модели.

Формы записи ЗЛП

Существует 3 формы записи ЗЛП:

1) в виде функций

max( или min)Z=,max( или min)Z=,

2) векторная форма

(скалярное произведение векторов)

3) матричная форма

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

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные xj налагаются условия неотрицательности, то она называется задачей линейного программирования в канонической форме или канонической задачей линейного программирования (КЗЛП).

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

Правила приведения ЗЛП к каноническому виду:

1) если в ограничениях правая часть отрицательная, то следует умножить это ограничение на -1;

2) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

3) если некоторая переменная xk не имеет ограничений по знаку, то она заменяется в целевой функции и во всех ограничениях разностью между двумя новыми неотрицательными переменными: xk=x * k — xl, где l — сводный индекс, x * k>=, xl>=0.

Рассмотрим пример. Приведем к канонической форме:

Введем в каждое уравнение системы ограничений выравнивающие переменные х4, х5, х6. Система запишется в виде равенств, причем в первое и третье уравнение системы ограничений переменные х4, х6 вводятся в левую часть со знаком «+», а во второе уравнение вводится х5 со знаком «-».

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

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

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

оптимизационный симплексный линейный программирование

Виды задач линейного программирования, способы их решения Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Дунаев Д. Н.

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

Похожие темы научных работ по математике , автор научной работы — Дунаев Д. Н.

Текст научной работы на тему «Виды задач линейного программирования, способы их решения»

ВИДЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, СПОСОБЫ ИХ РЕШЕНИЯ

Уфимский государственный авиационный технический университет,

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

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

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

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

2(х) = СХ + С2Х2 + . + СгХп (1)

определенной на некотором выпуклом подмножестве п-мерного пространства. Данное подмножество задается системой уравнений и неравенств:

ацХ] + $12X2 + $13X3 + . + апхп — Ь а2Х + $22X2 + $23X3 + . + а2пхп — Ь $31X1 + $32X2 + $33X3 + . + а3пхп — Ь

am1X1 + am2X2 + am3X3 + . • • + amnxn — Ьп x1 , x2, x3, . • •, Хп

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

* Аспирант кафедры Автоматизированных систем управления.

Задача линейного программирования может:

— иметь единственное решение;

— иметь бесчисленное множество решений;

Читать еще:  Ограниченный тип данных паскаль

— не иметь решения:

• из-за несовместимости системы ограничений;

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

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

Графический способ решения ЗЛП может применяться, в случае если целевая функция содержит две, реже три, неизвестные переменные.

Рассмотрим на примере. Найти максимальное значение целевой функции:

при следующих ограничениях:

Система неравенств (4) образует многоугольник ОЛБСБ допустимых решений (рис. 1).

Рис. 1. Область допустимых решений

Вершины ОЛБСБ называются опорными планами. Если задача имеет единственное решение, то оптимальный план совпадает с одним из опорных планов. Линейная целевая функция на графике перпендикулярна целевому вектору (3; 2) и свое максимальное значение принимает в точке С (3,33; 1,33) = 12.66.

Графический метод очень нагляден, но изобразить графически «-мерное пространство при п > 3 не представляется возможным. В подобных случаях применяются другие методы, описанные ниже.

В 1949 году американский математик Джордж Бернард Данциг разработал эффективный метод решения задач линейного программирования (ЗЛП) -симплекс-метод. Основное свойство симплекс метода заключает в его ите-рационности. На каждом этапе алгоритм переходит к новому опорному плану, улучшая значение целевой функции. Когда улучшение целевой функции невозможно процесс останавливается. Решение задачи симплекс методом предполагает множество однотипных операций, поэтому компьютер становится незаменимым инструментом.

Симплекс метод применим только к задаче в канонической форме. Для перехода от стандартной задачи к канонической необходимо:

1. обеспечить положительность всех свободных членов Ь. Если свободный член отрицателен, то все неравенство умножается на -1, знак неравенства при этом меняется на противоположенный;

2. Все неравенства преобразуются в равенства путем добавления дополнительных переменных. Если знак неравенства «меньше либо равно», то дополнительная переменная включается со знаком «+», в противном случае со знаком «-».

В каноническом виде система примет вид:

ацх1 + а12х2 + а13х3 + . + а1пхп + хп+1 = Ь1

а2х + а22х2 + а2эхэ + . + а2«х« + х«+2 = Ь2

ат1х1 + ат2х2 + ат3х3 + . • • + атпхп + хп+т Ьт хЬ ^ хЪ хп+т > 0

Ьь Ь2, Ьэ, . Ьт > 0

1. Нахождение первоначально базисного решения.

2. Переход к лучшему плану путем преобразования Гаусса-Жордана.

3. Проверка решения на оптимальность.

М переменных системы т линейных уравнений с п переменными, коэффициенты при которых образуют единичную матрицу называют базисными переменными.

Базисным решением системы т линейных уравнений с п переменными называется решение, в котором п — т небазисных переменных равны нулю.

В случае если все неравенства системы имеют условие «меньше либо равно», то дополнительные переменные образуют единичную матрицу. Принимая их за базисные, а остальные приравнивая к нулю получаем первоначальное базисное решение. Если не удается найти базисного решения, то в

уравнения с условием «больше либо равно» вводятся искусственные переменные. В случае наличия искусственных переменных применяется двух-этапный симплекс метод или м-метод.

3. Метод Штифеля.

Помимо метода Гаусса-Жордана существует еще один метод преобразования систем линейных уравнений — метод жордановых исключений. Применительно к задачам линейного программирования, данный метод получил название метода Штифеля.

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

4. Методы целочисленного линейного программирования (ЦЛП).

ЦЛП предназначено для решения задач, в которых все или некоторые переменных должны принимать дискретные или целочисленные значения. Несмотря на интенсивные исследования известные вычислительные методы решения задач ЦЛП далеки от совершенства.

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

Методы решения задач ЦЛП основаны на использовании вычислительных возможностей методов линейного программирования. Обычно алгоритмы ЦЛП включают три шага [1]:

1. «Ослабление» пространства допустимых решений задачи ЦЛП путем замены любой двоичной переменной у непрерывным ограничением 0

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

Дата публикации: 23.10.2019 2019-10-23

Статья просмотрена: 36 раз

Библиографическое описание:

Гребенникова Ю. В. Задачи линейного программирования в школьном курсе математики // Молодой ученый. — 2019. — №43. — С. 236-239. — URL https://moluch.ru/archive/281/63249/ (дата обращения: 03.04.2020).

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

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

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

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

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

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

Виды

тканей

Расход ткани на изготовление одного костюма

(условных единиц)

Запасы тканей

(тыс. усл. ед.)

Мужские костюмы

Женские костюмы

Известно, что реализация одного мужского костюма приносит доход в 3 условных единиц, а одного женского — 4 условных единиц. Требуется составить оптимальный план выпуска товаров, то есть такой план, при котором с учётом имеющихся ресурсов тканей доход от реализации костюмов будет наибольшим.

Построим математическую модель задачи. Введём переменные — количество мужских и женских костюмов соответственно (тыс. шт.). Тогда суммарный доход от их реализации определяется выражением

,

которое нужно максимизировать. По имеющимся исходным данным определяем ограничения по ресурсам каждого вида тканей. Они определяются неравенствами:

— для тканей вида ;

— для тканей вида ;

— для тканей вида ;

— для тканей вида .

Количество выпускаемых костюмов есть величина неотрицательная, поэтому Таким образом, получаем:

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

Читать еще:  Турбо паскаль обучение

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

В результате получим:

Значит, — точка максимума, и тогда

.

Таким образом, фабрике следует выпускать 4 тысячи мужских костюмов и 6 тысяч женских костюмов, при этом доход будет наибольшим и составит 36 тысяч условных единиц.

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

  1. Антонюк, Т. П. Задачи линейного программирования. Т. П. Антонюк // г. Ижевск. Ижевская областная типография, 2008–365с.
  2. Дорофеев, Г. В. Математика. 5 класс. Часть 1. Л. Г. Петерсон// М.: ООО «БИНОМ. Лаборатория знаний»
  3. Дорофеев, Г. В. Математика. 5 класс. Часть 2. Л. Г. Петерсон// М.: ООО «БИНОМ. Лаборатория знаний»
  4. Виленкин, А. Н. Математика 5 класс. Часть 1, А. Н. Виленкин., В. И. Жохов., А. С. Чесноков// М.: Просвещение
  5. Виленкин, А. Н. Математика 5 класс. Часть 2, А. Н. Виленкин., В. И. Жохов., А. С. Чесноков// М.: Просвещение
  6. Дорофеев, Г. В. Математика. 5 класс. Г. В. Дорофеев, И. Ф. Шарыгин, С. Б. Суворова// Под ред. Г. В. Дорофеева, И. Ф. Шарыгина. — М.: Просвещение
  7. Дорофеев, Г. В. Математика. 6 класс. Г. В. Дорофеев, И. Ф. Шарыгин, С. Б. Суворова// Под ред. Г. В. Дорофеева, И. Ф. Шарыгина. — М.: Просвещение
  8. Никольская, И. Л. Учимся рассуждать и доказывать. И. Л. Никольская, Е. Е. Семенов // Книга для учащихся 6–10 кл. сред.шк.-М.: Просвещение, 1989. –С. 192.
  9. Матюшкин, А. М. Проблемные ситуации в мышлении и обучении/ А. М. Матюшкин — М.:«Педагогика», 2007. — 198 с.
  10. Атанасян, Л. С. Методика преподавания математики в средней школе. / Л. С. Атанасян, — М.: Просвещение, 2012. — 368 с.

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

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

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

или min

(линейной функции элементов решения ) при линейных ограничительных условиях, накладываемых на элементы решения:

где — заданные числа.

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

Ведь в данном случае целевая функция z=ax+by –задает уравнение плоскости в декартовой системе координат,

Задают область в плоскости xOy.

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

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

Вникать в эти методы решения на данном этапе нет смысла.

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

Наиболее удобной программой для решения задач линейного программирования является встроенная надстройка в Excel Поиск Решения. Как с помощью этой надстройки решать задачи линейного программирования мы познакомимся на следующем уроке уже на конкретном примере.

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

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

Оптимальное распределение должно минимизировать суммарные издержки.

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

1. Задаем вопрос. Что мы хотим получить?

2. Определяем тип целевой функции максимум(обычно для прибыли) или минимум (для суммарных издержек).

3. Определяем переменные, которые будем варьировать Xi, составляем целевую функцию,

4. Определяем граничные условия.

5. Решаем задачу, если мало переменных то графическим способом, если много то с помощью приближенных методов с использованием специальных программ.

6. Проверяем решение на непротиворечивость. (если решение явно неверное, то возможны два случая :неверно определены параметры, либо не все условия мы учли).

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

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

Задача о диете (рационе)

Одна женщина посоветовала подруге перейти на рациональное питание, состоящее из двух продуктов P и Q.Суточное питание этими продуктами должно давать не более 14 единиц жира (чтобы похудеть), но не менее 300 калорий. На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на упаковке с продуктом Q — 4 единицы жира и 200 калорий соответственно. При этом цена 1 килограмма продукта Р равна 15 руб., а 1 кг продукта Q — 25 руб. Так как дама была стеснена в средствах, но ее интересовал вопрос: в какой пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и истратить как можно меньше денег?

Перейдем к формализации данной ситуации на языке математических символов. Обозначим через х количество продукта Р и через у количество продукта Q, требуемые для выполнения условий диеты. Количество единиц жира, содержащегося в х кг продукта Р и в у кг продукта Q, равно 15х + 4 и по условию диеты не должно превосходить 14:

В свою очередь, количество калорий, содержащихся в х кг продукта Р и в у кг продукта Q, равно 150х + 200у и по условию диеты должно быть не меньше 300:

Теперь о стоимости z продуктов. Она равна

и в соответствии с высказанными пожеланиями должна быть минимальной. Последнее записывается так:

Тем самым мы получили систему формул:

которую решим графическим способом.

Нас интересует только та ее часть, которая лежит над треугольником BDE. Вычисляя значения z во всех трех вершинах этого треугольника

и сравнивая полученные результаты, замечаем, что наименьшее значение (35) достигается в вершине Е. Таким образом,

В общем виде задача о диете, оптимальном рационе.

Кол-во единиц питательных веществ, содержащихся в единице продукции вида

Ссылка на основную публикацию
ВсеИнструменты 220 Вольт
Adblock
detector