🗊 Задачи линейного программирования Лекция 3

Категория: Информатика
Нажмите для полного просмотра!
Задачи линейного программирования Лекция 3 , слайд №1 Задачи линейного программирования Лекция 3 , слайд №2 Задачи линейного программирования Лекция 3 , слайд №3 Задачи линейного программирования Лекция 3 , слайд №4 Задачи линейного программирования Лекция 3 , слайд №5 Задачи линейного программирования Лекция 3 , слайд №6 Задачи линейного программирования Лекция 3 , слайд №7 Задачи линейного программирования Лекция 3 , слайд №8 Задачи линейного программирования Лекция 3 , слайд №9 Задачи линейного программирования Лекция 3 , слайд №10 Задачи линейного программирования Лекция 3 , слайд №11 Задачи линейного программирования Лекция 3 , слайд №12 Задачи линейного программирования Лекция 3 , слайд №13 Задачи линейного программирования Лекция 3 , слайд №14 Задачи линейного программирования Лекция 3 , слайд №15 Задачи линейного программирования Лекция 3 , слайд №16 Задачи линейного программирования Лекция 3 , слайд №17 Задачи линейного программирования Лекция 3 , слайд №18 Задачи линейного программирования Лекция 3 , слайд №19 Задачи линейного программирования Лекция 3 , слайд №20 Задачи линейного программирования Лекция 3 , слайд №21 Задачи линейного программирования Лекция 3 , слайд №22 Задачи линейного программирования Лекция 3 , слайд №23 Задачи линейного программирования Лекция 3 , слайд №24 Задачи линейного программирования Лекция 3 , слайд №25 Задачи линейного программирования Лекция 3 , слайд №26 Задачи линейного программирования Лекция 3 , слайд №27 Задачи линейного программирования Лекция 3 , слайд №28 Задачи линейного программирования Лекция 3 , слайд №29 Задачи линейного программирования Лекция 3 , слайд №30 Задачи линейного программирования Лекция 3 , слайд №31 Задачи линейного программирования Лекция 3 , слайд №32 Задачи линейного программирования Лекция 3 , слайд №33 Задачи линейного программирования Лекция 3 , слайд №34 Задачи линейного программирования Лекция 3 , слайд №35 Задачи линейного программирования Лекция 3 , слайд №36 Задачи линейного программирования Лекция 3 , слайд №37 Задачи линейного программирования Лекция 3 , слайд №38 Задачи линейного программирования Лекция 3 , слайд №39 Задачи линейного программирования Лекция 3 , слайд №40 Задачи линейного программирования Лекция 3 , слайд №41
Скачать

Содержание ▲

Вы можете ознакомиться и скачать Задачи линейного программирования Лекция 3 . Презентация содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Задачи линейного программирования Лекция 3
Описание слайда:
Задачи линейного программирования Лекция 3

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


Здесь -неизвестные, -заданные постоянные величины. Ограничения могут быть заданы уравнениями. Наиболее часто встречаются задачи в виде: имеется ресурсов при ограничениях. Нужно определить объемы этих ресурсов , при которых целевая функция будет достигать максимума (минимума), т. е. найти оптимальное распределение ограниченных ресурсов. При этом имеются естественные ограничения >0.
Описание слайда:
Здесь -неизвестные, -заданные постоянные величины. Ограничения могут быть заданы уравнениями. Наиболее часто встречаются задачи в виде: имеется ресурсов при ограничениях. Нужно определить объемы этих ресурсов , при которых целевая функция будет достигать максимума (минимума), т. е. найти оптимальное распределение ограниченных ресурсов. При этом имеются естественные ограничения >0.

Слайд 6


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

Слайд 7


В краткой записи ЗЛП имеет вид: при ограничениях
Описание слайда:
В краткой записи ЗЛП имеет вид: при ограничениях

Слайд 8


Для составления математической модели ЗЛП необходимо : 1)обозначить переменные; 2)составить целевую функцию; 3)записать систему ограничений в соответствии с целью задачи; 4)записать систему ограничений с учетом имеющихся в условии задачи показателей. Если все ограничения задачи заданы уравнениями, то модель такого вида называется канонической. Если хоть одно из ограничений дано неравенством, то модель неканоническая.
Описание слайда:
Для составления математической модели ЗЛП необходимо : 1)обозначить переменные; 2)составить целевую функцию; 3)записать систему ограничений в соответствии с целью задачи; 4)записать систему ограничений с учетом имеющихся в условии задачи показателей. Если все ограничения задачи заданы уравнениями, то модель такого вида называется канонической. Если хоть одно из ограничений дано неравенством, то модель неканоническая.

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


Примеры
Описание слайда:
Примеры

Слайд 14


Допустим, что будет изготовлено изделий вида А, -изделий вида В и -изделий вида С. Тогда для производства такого количества изделий потребуется затратить станко-часов фрезерного оборудования. Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство
Описание слайда:
Допустим, что будет изготовлено изделий вида А, -изделий вида В и -изделий вида С. Тогда для производства такого количества изделий потребуется затратить станко-часов фрезерного оборудования. Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство

Слайд 15


Рассуждая аналогично, можно составить систему ограничений
Описание слайда:
Рассуждая аналогично, можно составить систему ограничений

Слайд 16


Теперь составим целевую функцию. Прибыль от реализации изделий вида А составит 10 , от реализации -изделий вида В -14 и от реализации -изделий вида С-12 Общая прибыль от реализации всех изделий составит
Описание слайда:
Теперь составим целевую функцию. Прибыль от реализации изделий вида А составит 10 , от реализации -изделий вида В -14 и от реализации -изделий вида С-12 Общая прибыль от реализации всех изделий составит

Слайд 17


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

Слайд 18


Пример 2 Продукцией гормолокозавода являются молоко, кефир и сметана, расфасованные в тару. На производство 1 т молока, кефира и сметаны требуется соответственно1010,1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 часов.
Описание слайда:
Пример 2 Продукцией гормолокозавода являются молоко, кефир и сметана, расфасованные в тару. На производство 1 т молока, кефира и сметаны требуется соответственно1010,1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 часов.

Слайд 19


Всего для производства цельномолочной продукции завод может использовать 136000 кг молока. Основное оборудование может быть занято в течение 21,4 машино-часов, а автоматы по расфасовке сметаны – в течение 16,25 часов. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции нет ограничений.
Описание слайда:
Всего для производства цельномолочной продукции завод может использовать 136000 кг молока. Основное оборудование может быть занято в течение 21,4 машино-часов, а автоматы по расфасовке сметаны – в течение 16,25 часов. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции нет ограничений.

Слайд 20


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

Слайд 21


Решение Пусть завод будет производить т молока, т кефира и т сметаны. Тогда ему необходимо кг молока. Так как завод может использовать ежедневно не более 136000 кг молока, то должно выполняться неравенство
Описание слайда:
Решение Пусть завод будет производить т молока, т кефира и т сметаны. Тогда ему необходимо кг молока. Так как завод может использовать ежедневно не более 136000 кг молока, то должно выполняться неравенство

Слайд 22


Ограничения на время по расфасовке молока и кефира и по расфасовке сметаны . Так как ежедневно должно вырабатываться не менее100 т молока, то . По экономическому смыслу
Описание слайда:
Ограничения на время по расфасовке молока и кефира и по расфасовке сметаны . Так как ежедневно должно вырабатываться не менее100 т молока, то . По экономическому смыслу

Слайд 23


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

Слайд 24


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

Слайд 25


Таблица
Описание слайда:
Таблица

Слайд 26


Решение Общая стоимость рациона при ограничениях с учетом необходимого минимума питательных веществ
Описание слайда:
Решение Общая стоимость рациона при ограничениях с учетом необходимого минимума питательных веществ

Слайд 27


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

Слайд 28


Введем обозначения: -количество j-го материала, входящего в смесь; -цена материала j-го вида; -это минимально необходимое содержание i-го компонента в смеси. Коэффициенты показывают удельный вес i-го компонента в единице j-го материала
Описание слайда:
Введем обозначения: -количество j-го материала, входящего в смесь; -цена материала j-го вида; -это минимально необходимое содержание i-го компонента в смеси. Коэффициенты показывают удельный вес i-го компонента в единице j-го материала

Слайд 29


Экономико-математическая модель задачи. Целевая функция представляет собой суммарную стоимость смеси, а функциональные ограничения являются ограничениями по содержанию компонентов в смеси: смесь должна содержать компоненты в объемах, не менее указанных.
Описание слайда:
Экономико-математическая модель задачи. Целевая функция представляет собой суммарную стоимость смеси, а функциональные ограничения являются ограничениями по содержанию компонентов в смеси: смесь должна содержать компоненты в объемах, не менее указанных.

Слайд 30


Задача о раскрое На швейной фабрике ткань может быть раскроена несколькими способами для изготовления нужных деталей швейных изделий. Пусть при j-ом варианте раскроя изготавливается деталей i-го вида, а величина отходов при данном варианте раскроя равна Зная, что деталей i-го вида следует изготовлять штук, требуется раскроить ткань так, чтобы было получено необходимое количество деталей каждого вида при минимальных общих отходах. Составить математическую модель задачи.
Описание слайда:
Задача о раскрое На швейной фабрике ткань может быть раскроена несколькими способами для изготовления нужных деталей швейных изделий. Пусть при j-ом варианте раскроя изготавливается деталей i-го вида, а величина отходов при данном варианте раскроя равна Зная, что деталей i-го вида следует изготовлять штук, требуется раскроить ткань так, чтобы было получено необходимое количество деталей каждого вида при минимальных общих отходах. Составить математическую модель задачи.

Слайд 31


Решение. Предположим, что по j-ому варианту раскраивается сотен ткани. Поскольку при раскрое ткани по j-ому варианту получается деталей i-го вида , по всем вариантам раскроя из используемых тканей будет получено Общая величина отходов по всем вариантам раскроя составит
Описание слайда:
Решение. Предположим, что по j-ому варианту раскраивается сотен ткани. Поскольку при раскрое ткани по j-ому варианту получается деталей i-го вида , по всем вариантам раскроя из используемых тканей будет получено Общая величина отходов по всем вариантам раскроя составит

Слайд 32


Таким образом, приходим к следующей задаче: Найти минимум функции при условии, что ее переменные удовлетворяют ограничениям
Описание слайда:
Таким образом, приходим к следующей задаче: Найти минимум функции при условии, что ее переменные удовлетворяют ограничениям

Слайд 33


Общая задача линейного программирования. Опр.1.Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (1) при условиях (2) где -заданные постоянные величины и
Описание слайда:
Общая задача линейного программирования. Опр.1.Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (1) при условиях (2) где -заданные постоянные величины и

Слайд 34


Опр.2.Функция (1) называется целевой, а условия (2)-ограничениями задачи. Опр.3. Совокупность чисел , удовлетворяющих ограничениям задачи (1)-(2), называются допустимым решением (или планом).
Описание слайда:
Опр.2.Функция (1) называется целевой, а условия (2)-ограничениями задачи. Опр.3. Совокупность чисел , удовлетворяющих ограничениям задачи (1)-(2), называются допустимым решением (или планом).

Слайд 35


Основная задача ЛП Опр.4. Основной , или канонической ЗЛП называется задача, состоящая в определении значения целевой функции при условии, что система ограничений представлена в виде системы уравнений:
Описание слайда:
Основная задача ЛП Опр.4. Основной , или канонической ЗЛП называется задача, состоящая в определении значения целевой функции при условии, что система ограничений представлена в виде системы уравнений:

Слайд 36


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

Слайд 37


Пример. Записать в форме основной задачи ЛП задачу: найти максимум функции при условиях
Описание слайда:
Пример. Записать в форме основной задачи ЛП задачу: найти максимум функции при условиях

Слайд 38


Перейдем от ограничений –неравенств к ограничениям-равенствам. У нас имеется 4 неравенства, поэтому введем 4 дополнительные переменные. Тогда запишем уже основную задачу линейного программирования: максимизировать функцию при условиях
Описание слайда:
Перейдем от ограничений –неравенств к ограничениям-равенствам. У нас имеется 4 неравенства, поэтому введем 4 дополнительные переменные. Тогда запишем уже основную задачу линейного программирования: максимизировать функцию при условиях

Слайд 39


Свойства основной ЗЛП. Перепишем ЗЛП в векторной форме: найти максимум функции при условиях Здесь
Описание слайда:
Свойства основной ЗЛП. Перепишем ЗЛП в векторной форме: найти максимум функции при условиях Здесь

Слайд 40


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

Слайд 41


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию