Letysite.ru

IT Новости с интернет пространства
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грн.

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

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

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

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

Читать еще:  Низкоуровневые языки программирования

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

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

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

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

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

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

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина » математическое программирование «. Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина » линейное программирование » возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

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

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

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

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

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

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

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

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

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

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

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

Задача условной оптимизации называется задачей линейного программирования (ЛП), если целевая функция и все функции ограничений являются линейными функциями: (5.1)
где ci,bj,aij постоянные коэффициенты. Это есть стандартная форма задачи ЛП. В общем случае ограничения могут иметь знак „» или „=». Однако, умножая неравенство на -1 и заменяя равенство двумя неравенствами „≤» и „≥», можно придти к стандартной форме. Кроме того, взяв вместо f(x) функцию — f(x), можно получить задачу на минимум.
Обозначим через c=(c1 ,…,cn) — вектор коэффициентов целевой функции, b =(b1,…,bk) — вектор свободных членов ограничений, — матрицу коэффициентов ограничений и запишем нашу задачу в векторной форме: (5.2)
где — скалярное произведение двух векторов c и x. Такая компактная запись удобна для теоретических исследований.
Несколько примеров задач, которые сводятся к задачам линейного программирования:

Задача оптимального раскроя материала. Фирма изготовляет изделие состоящее из р деталей. Причем в одно изделие эти детали входят в количествах k1 . kr . С этой целью производится раскрой m партий материала. В i-ой партии имеется bi единиц материала. Каждую единицу материала можно раскроить на детали n способами. При раскрое единицы i-ой партии j-м способом получается аijr деталей r-го вида. Требуется составить такой план раскроя материала, чтобы из них получить максимальное число изделий.

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

Задача о назначениях на работу. Имеется n работ и n исполнителей. Стоимость выполнения работы i исполнителем j равна cij. Нужно распределить исполнителей на работы так, чтобы минимизировать затраты на оплату труда.

3адача о смесях (о рационе). Из m видов исходных материалов каждый из которых состоит из n компонент, составить смесь, в которой содержание компонент должно быть не меньше b1 . bn. Известны цены единиц материалов с1 . сm и удельный вес j-го компонента в единице i-го материала. Требуется составить смесь, в которой затраты будут минимальными.

Задача о рюкзаке. Имеется n предметов. Вес предмета i равен рi , ценность – сi (i=1. n). Требуется при заданной ценности груза выбрать совокупность предметов минимального веса.

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

Для любой задачи ЛП можно составить двойственную к ней задачу по следующим правилам.
1. Привести исходную задачу ЛП к стандартной форме.
2. Ввести новые переменные по числу основных ограничений исходной задачи.
3. Составить новые ограничения из новых переменных в виде линейных неравенств, знаки которых противоположны знакам неравенств исходной задачи, коэффициентами которых служат элементы транспонированной матрицы исходной задачи, а свободными членами — коэффициенты при целевой функции исходной задачи.
4. Для новых переменных написать условия неотрицательности.
В результате для исходной задачи (5.1) получим следующую двойственную задачу ЛП: (5.3)
Задача (5.1) относительно задачи (5.3) называется прямой задачей ЛП . Векторная форма задачи (5.3) имеет вид: (5.4)
Рассмотрение взаимно двойственных задач ЛП полезно как с теоретической, так и с практической точек зрения. Это видно из следующих утверждений.
1. Если одна из задач (5.1) и (5.3) имеет оптимальное решение, то и другая имеет оптимальное решение, причем
2. Если целевая функция одной из задач неограниченна, то ограничения другой задачи несовместны (т.е. множество допустимых решений пусто).
3. Для того, чтобы допустимое решение и были оптимальными решениями соответствующих задач (5.1) и (2.3) , необходимо и достаточно, чтобы

4. Для любых допустимых решений x 0 и y 0 справедливо неравенство f(x 0 ) ≤ z(y 0 ); если f(x 0 ) = z(y 0 ), то x 0 и y 0 — оптимальные решения задач (5.1) и (5.3).
5. Если прямая задача (5.1) моделирует максимизацию дохода при ограниченных ресурсах, то двойственная задача (5.3) при тех же предпосылках моделирует минимизацию затрат при фиксированном уровне дохода.

Читать еще:  Как отключить систему безопасности

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

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

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

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

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

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

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

6. Задача составления расписания – очередность выполнения операций, на различных видах оборудования.

7. Задача планирования и размещения производственных объектов – т.е. оптимального числа и места их размещения, а также новых объектов с учетом их взаимодействия с существующими объектами и между собой.

8. Задача выбора маршрута (сетевые задачи) – возникают на транспорте, и в системе связи, необходимо найти наиболее экономичные маршруты;

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

10. Многокритериальные задачи – успех в которых классифицируется не по одному, а по нескольким критериям, из которых одни следует минимизировать, а другие максимизировать. В таких задачах решение отыскивается путем выделения критериев.

Общие этапы решения задач исследования операций и их назначение

a. Формализация исходной проблемы – это начальный этап;

· Описание всего множества возможных (альтернативных решений);

· Определение целевой функции т.е. формализация на математическом языке преследуемой выгоды (цели);

· Построение системы ограничений

b. Построение математической модели;

c. Решение/реализация модели;

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

e. Анализ и реализация решения.

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

Этот метод является наиболее простым, он предназначения для решения задач имеющих две переменные.

Графический метод включает в себя два этапа:

1. Построение пространства (множества) допустимых решений, удовлетворяющих всем заданным ограничениям;

2. Нахождение оптимального решения среди всех точек (решений) в этом пространстве.

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

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

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

Эта задача проще общей задачи линейного программирования, поскольку ее ограничения имеют весьма специальный вид. Интересно, что к транспортной задаче сводятся проблемы планирования экономических объектов разного типа. Поэтому были предприняты значительные усилия по построению эффективных методов решения транспортной задачи, и эти усилия увенчались успехом. В настоящее время умеют решать задачи транспортного типа значительно быстрее и с большим числом неизвестных, чем обычные задачи [c.151]

Такие задачи математически бывают представлены в двух видах в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. [c.290]

Читать еще:  Язык программирования modula

В каждый момент времени решение имеет базисное представление. Это справедливо, в частности, для момента t=To=0. Можно видеть, что при фиксированном времени задача превращается в задачу 6 потоке минимальной стоимости [68] с ограничениями на поток снизу (одна из специальных задач линейного программирования) [c.130]

При решении задач линейного программирования большой размерности постоянно приходится иметь в виду следующие два обстоятельства. Во-первых, решение задач с большим числом переменных и ограничений ведет к частому использованию устройств внешней памяти ЭВМ, которые характеризуются относительно невысоким быстродействием, что в конечном счете приводит к значительному расходу машинного времени. Во-вторых, очень часто возникающие из нужд практики задачи обладают той или иной специальной структурой (матрица ограничений симметрична, имеет блочную структуру, содержит много нулей и т. п.). Хотя сама задача в этом случае и не может быть решена с помощью специальных методов решения, но отдельные ее части — задачи меньшего объема — могут быть эффективно разрешены с помощью некоторых специальных методов. [c.43]

В первой главе были рассмотрены некоторые методы решения общей задачи линейного программирования. На практике, однако, нередко приходится иметь дело не с самой общей задачей, а со специальными видами задач, порожденными отдельными классами экономических моделей. Конечно, для поиска оптимальных решений в этих моделях могут использоваться и общие методы, однако, как правило, более выгодно при решении этих задач учитывать их специфику. [c.45]

Формально необходимо определить оптимум функции (4.88) при условиях (4.89). Нетрудно видеть, что рассматриваемая задача относится к простым задачам дробно-линейного программирования, которые эффективно могут быть решены методом сведения их к задачам ЛП 1931. Однако в данном случае ввиду простоты системы ограничений удалось найти специальный, более конструктивный алгоритм, позволяющий, кроме прочего, определить в эффективной форме и критерий оптимальности рассматриваемой задачи. [c.137]

Таким образом, задача описывается моделью линейного программирования, имеющей 19 ограничений в форме равенств и неравенств и 13 переменных (последние два ограничения в блоке 4 в силу неотрицательности искомых переменных выполняются всегда, и их можно не учитывать). Оптимальное решение, найденное с помощью специальной компьютерной программы на ПК IBM P /AT, имеет вид [c.411]

Как мы видели, наиболее трудная часть решения двухэтапной задачи стохастического программирования—определение предварительного плана — сводится к решению эквивалентной детерминированной задачи. Доказано, что эквивалентная задача является задачей выпуклого программирования. Однако в общем случае для ее решения стандартные методы выпуклого программирования неприменимы. Дело в том, что как целевая функция, так и область определения планов общей двухэтапной задачи заданы неявно. Показатель качества решения эквивалентной задачи далеко не всегда представляет собой дифференцируемую функцию. Вычисление параметров задачи, используемых в стандартных методах решения выпуклых задач, сопряжено со значительными трудностями. Существующие методы решения двухэтапных задач стохастического программирования используют специфические особенности эквивалентной детерминированной задачи. В настоящем параграфе рассмотрены общие и специальные методы вычисления предварительного плана и некоторые неравенства, позволяющие получить и оценить приближенные решения эквивалентной задачи. Ясно, что во всех частных случаях, в которых удается получить явную запись эквивалентной задачи в виде простой линейной, кусочно-линейной или выпуклой задачи, нет необходимости прибегать к предлагаемым здесь, вообще говоря, трудоемким методам. [c.180]

Арбузова Н. И. Взаимосвязь стохастической е-устойчивости задач линейного и дробно-линейного программирования специального вида. — Экономика и математические методы , 1968, т. IV, вып. 1, с. 108—ПО. [c.381]

ПРОГРАММИРОВАНИЕ — составление программ для решения задач на ЭВМ, выбор метода решения, приведение уравнений к виду, удобному для решения на ЭВМ, подготовка исходных данных для постановки задачи, требующей решения наука, занимающаяся разработкой средств и методов подготовки программ для ЭВМ. Программирование включает представление хода решения задачи в виде инструкций, для записи которых разработаны специальные языки (языки программирования или алгоритмические), воспринимаемые ЭВМ. С помощью принятых уравнений, отражающих реальные зависимости между явлениями, по исходным данным определяются значения искомых переменных, совокупность которых может представлять собой параметры плана работы предприятия, объединения, отрасли. В зависимости от формы взаимосвязи между исходными данными и искомыми величинами различают программирование линейное, нелинейное, динамическое и др. Линейное программирование означает прямую пропорциональную зависимость между исходными данными и ис- [c.241]

Более широкие возможности имеет пакет Стохастическая оптимизация», созданный на базе ППП Линейное программирование в АСУ» (ППП ЛП АСУ) [102]. ППП ЛП АСУ предназначен для решения и анализа задач линейного программирования (ЛП), нелинейного программирования (НЛП) с нелинейными функциями сепарабельного вида, целочисленного программирования (ЦП) и задач специальной узкоблочной структуры. Размерность решаемых задач составляет для ЛП до 16000 строк, для ЦП — до 4095 целочисленных переменных и 60000 строк для задач узкоблочной структуры. Пакет может быть использован также для решения задач стохастического программирования (СТП) при построчных вероятностных ограничениях. В последнем случае необходимо предварительно построить детерминированный аналог. [c.179]

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

Задачи вида (25.27) решаются методами математического программирования, которое включает в себя линейное, нелинейное, динамическое, целочисленное программирование и т.д. Выбор методов математического программирования для решения оптимизационных задач определяется видом целевой функции /, видом ограничений, определяющих область М, и специальными ограничениями на управляемые переменные (например, требованием их целочисленности). Решение задачи получения управнения (25.27) обычно называется оптимальным решением, или оптимальным планом. [c.523]

Ссылка на основную публикацию
Adblock
detector