Разделы презентаций


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

Содержание

1. Графическое решение задачи линейного программирования 1. Строится многоугольная допустимая область решений (ОДР), соответствующая ограничениям 2. Строится вектор–градиент линейной формы с координатами 3. Строится прямая , перпендикулярная вектору-градиенту. Прямая «передвигается»

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

Слайд 1Тема 2. Линейное программирование
1. Графическое решение ЗЛП
2. Особые случаи решения

ЗЛП графическим методом
3. Основы симплекс-метода
4. Транспортная задача

Тема 2. Линейное программирование1. Графическое решение ЗЛП2. Особые случаи решения ЗЛП графическим методом3. Основы симплекс-метода4. Транспортная задача

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

область решений (ОДР), соответствующая ограничениям
2. Строится вектор–градиент линейной формы

с координатами



3. Строится прямая , перпендикулярная вектору-градиенту. Прямая «передвигается» в направлении этого вектора в случае максимизации (в направлении, противоположном вектору - в случае минимизации) до тех пор, пока не покинет пределов многоугольной области.
4. Определяются координаты предельной точки.
Подставляются значения координат в выражение целевой функции, тем самым находятся ее экстремальные значения.

1. Графическое решение задачи линейного программирования 1.  Строится многоугольная допустимая область решений (ОДР), соответствующая ограничениям 2.

Слайд 3Пример решения ЗЛП графическим методом
Пример 1.
f(х1,х2) = (2х1+3х2) → max
х1+3х2

 300
х1+х2  150
х1,2  0

1 этап.
х1+ 3х2

=300

(0;100) и (300;0).
Пример решения ЗЛП графическим методомПример 1.f(х1,х2) = (2х1+3х2) → maxх1+3х2  300х1+х2   150 х1,2 

Слайд 4
х1+х2 = 150

(0;150) и (150;0).

х1+х2 = 150 (0;150) и (150;0).

Слайд 5
х1+х2 = 150

(0;150) и (150;0).

х1+х2 = 150 (0;150) и (150;0).

Слайд 6 2 этап. Строится вектор-градиент с координатами ∆(100;150) .

3

этап. Строится прямая , перпендикулярная вектору-градиенту.

Прямая «передвигается» до момента покидания ОДР.
Предельная точка – точка В.









А

В

С

2 этап. Строится вектор-градиент с координатами ∆(100;150) . 3 этап. Строится прямая , перпендикулярная вектору-градиенту.

Слайд 74 этап.



х1+3х2 = 300 2х2

= 150

х1+х2 = 150

х1 = 75 х2

= 75


Т.к. координаты точки В равны х1 = 75 и х2 = 75, то максимум ЦФ равен 375.


f = 2х1+3х2 = 2·75 + 3·75 = 375
4 этап.х1+3х2 = 300      2х2 = 150х1+х2 = 150х1 = 75

Слайд 8Пример № 2 .
Совхоз для кормления

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

содержаться не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В.
Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы:
Пример № 2 .    Совхоз для кормления животных использует два вида корма. В дневном

Слайд 9Пример 2 .








х1 - кол-во

корма 1 вида
х2 - кол-во корма 2 вида
F(Х)= 0,2

х1 + 0,3х2 → min
2 х1 + х2 ≥ 6
2 х1 + 4х2 ≥ 12
х1 , х2 ≥ 0

Пример 2 .    х1 - кол-во корма 1 вида х2 - кол-во корма 2

Слайд 10Пример 2 .
F(Х)= 0,2 х1 + 0,3х2 → min


2 х1 + х2 ≥ 6
2 х1 + 4х2

≥ 12
х1 , х2 ≥ 0



2 х1 + х2 = 6



2 х1 + 4х2 ≥ 12

1

2

3

4

5

6

1

2

3

4

5

6

0

х1

х2

Пример 2 . F(Х)= 0,2 х1 + 0,3х2 → min 2 х1 + х2  ≥ 62

Слайд 11Пример 2 .
F(Х)= 0,2 х1 + 0,3х2 → min


2 х1 + х2 ≥ 6
2 х1 + 4х2

≥ 12
х1 , х2 ≥ 0

Предельная точка: В(2;2)
min F(X) = 0,2 *2 + 0,3*2 = 1


1

2

3

4

5

6

1

2

3

4

5

6

0

х1

х2

(4;6)

В

А

С

Пример 2 . F(Х)= 0,2 х1 + 0,3х2 → min 2 х1 + х2  ≥ 62

Слайд 13Особые случаи решения ЗЛП графическим методом
1 случай.
Область допустимых решений

пуста и ЗЛП решений не имеет.


х1

+ 2х2 = -10

(0;-5) и (10;0)
Особые случаи решения ЗЛП графическим методом1 случай. Область допустимых решений пуста и ЗЛП решений не имеет.

Слайд 142 случай.
ОДР – незамкнутый многоугольник в

направлении оптимизации целевой функции. Задача не имеет решений.

2 случай.    ОДР – незамкнутый многоугольник в направлении оптимизации целевой функции. Задача не имеет

Слайд 153 случай.
Решений бесконечно много.

3 случай.  Решений бесконечно много.

Слайд 162. Основы симплекс-метода
Подобно тому, как графический метод ищет оптимум в

вершинах многоугольника,
в симплексном методе оптимум ищется в вершинах n-мерного

многогранника, называемого симплексом.

2. Основы симплекс-метода Подобно тому, как графический метод ищет оптимум в вершинах многоугольника, в симплексном методе оптимум

Слайд 172. Основы симплекс-метода
Алгоритм симплекс-метода
1. Путем преобразований система ограничений приводится к

необходимой, так называемой базисной, форме.
2. Находится так называемое опорное решение,

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

2. Основы симплекс-метода Алгоритм симплекс-метода1. Путем преобразований система ограничений приводится к необходимой, так называемой базисной, форме.2. Находится

Слайд 181 вариант
Инвестор, располагающий суммой в 300 тыс. ден. ед.,

может вложить свой капитал в акции автомобильного концерна А и

строительного предприятия В.
Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причем последних можно купить не более чем на 100 тыс. ден. ед.
Дивиденды по акциям А составляют 8% в год, по акциям В – 10%. Какую максимальную прибыль можно получить в первый год?
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум и почему?

1 вариант Инвестор, располагающий суммой в 300 тыс. ден. ед., может вложить свой капитал в акции автомобильного

Слайд 191 вариант.
х1 – тыс. ден. ед. ,вложенных в акции

концерна А
х2 – тыс. ден. ед. , вложенных в акции

предприятия В
F (х) = 0,08 х1+0,10 х2 → max - общая прибыль
x1+ х2 ≤ 300
х1- 2х2 ≥ 0
х2 ≤ 100
х1, х2 ≥ 0
1 вариант. х1 – тыс. ден. ед. ,вложенных в акции концерна Ах2 – тыс. ден. ед. ,

Слайд 20 1 вариант.
х1 – тыс. ден. ед. ,вложенных в

акции концерна А
х2 – тыс. ден. ед. , вложенных в

акции предприятия В
F (х) = 0,08 х1+0,10 х2 → max - общая прибыль
x1+ х2 ≤ 300
х1- 2х2 ≥ 0
х2 ≤ 100
х1, х2 ≥ 0

1 вариант. х1 – тыс. ден. ед. ,вложенных в акции концерна Ах2 – тыс. ден. ед.

Слайд 21 1 вариант.
Инвестор, располагающий суммой в 300 тыс. ден.

ед., может вложить свой капитал в акции автомобильного концерна А

и строительного предприятия В.
Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В,
причем последних можно купить не более чем на 100 тыс. ден. ед.
Дивиденды по акциям А составляют 8% в год, по акциям В – 10%.
Какую максимальную прибыль можно получить в первый год?
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум и почему?


1 вариант. Инвестор, располагающий суммой в 300 тыс. ден. ед., может вложить свой капитал в акции

Слайд 223 вариант
Некоторая фирма выпускает два набора удобрений для газонов: обычный

и улучшенный.
В обычный набор входит 3 кг азотных,
4

кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений.
Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений.
Обычный набор стоит 3 ден. ед., а улучшенный – 4 ден. ед.
Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

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

Слайд 234 вариант
На имеющихся у фермера 400 гектарах земли он

планирует посеять кукурузу и сою.
Сев и уборка кукурузы требует

на каждый гектар 200 ден. ед. затрат, а сои – 100 ден. ед.
На покрытие расходов, связанных с севом и уборкой, фермер получил ссуду в 60 тыс. ден. ед..
Каждый гектар, засеянный кукурузой, принесет 30 центнеров, а каждый гектар, засеянный соей – 60 центнеров.
Фермер заключил договор на продажу, по которому каждый центнер кукурузы принесет ему 3 ден. ед., а каждый центнер сои – 6 ден. ед.
Однако, согласно этому договору, фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 21 тыс. центнеров.
Фермеру хотелось бы знать, сколько гектар нужно засеять каждой из этих культур, чтобы получить максимальную прибыль.

4 вариант На имеющихся у фермера 400 гектарах земли он планирует посеять кукурузу и сою. Сев и

Слайд 245 вариант
Продукция двух видов (краска для внутренних (I) и наружных

(Е) работ) поступает в оптовую продажу. Для производства красок используются

два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно.
Расходы продуктов А и В на 1 т соответствующих красок приведены в таблице.

 


Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3000 ден. ед. для краски Е и 2000 ден. ед. для краски I.
Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?
5 вариантПродукция двух видов (краска для внутренних (I) и наружных (Е) работ) поступает в оптовую продажу. Для

Слайд 256 вариант
Финансовый консультант фирмы «АВС» консультирует клиента по оптимальному инвестиционному

портфелю.
Клиент хочет вложить средства (не более 25000$) в два

наименования акций крупных предприятий в составе холдинга «Дикси».
Анализируются акции «Дикси –Е» и «Дикси –В». Цены на акции: «Дикси –Е» - 5$ за акцию; «Дикси –В» - 3$ за акцию.
Клиент уточнил, что он хочет приобрести максимум 6000 акций обоих наименований, при этом акций одного из наименований должно быть не более 5000 штук.
По оценкам «АВС» прибыль от инвестиций в эти две акции в следующем году составит: «Дикси –Е» - 1,1$; «Дикси –В» - 0,9$.
Задача консультанта состоит в том, чтобы выдать клиенту рекомендации по оптимизации прибыли от инвестиций.
6 вариантФинансовый консультант фирмы «АВС» консультирует клиента по оптимальному инвестиционному портфелю. Клиент хочет вложить средства (не более

Слайд 267 вариант
Завод-производитель высокоточных элементов для автомобилей выпускает два различных

типа деталей Х и Y.
Фонд рабочего времени равен 4000

чел.-ч в неделю.
Для производства одной детали типа Х требуется 1 чел./ч, а для производства одной детали типа Y – 2 чел./ч.
Производственные мощности завода позволяют выпускать максимум 2250 деталей Х и 1750 деталей Y в неделю.
Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла.
Уровень запасов каждого вида металла составляет 10000 кг в неделю.
Еженедельно завод поставляет 600 деталей типа Х своему постоянному заказчику.
По профсоюзному соглашению общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.
Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30 ден. ед., а от производства одной детали типа Y – 40 ден. ед.?
7 вариант Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей Х и Y. Фонд рабочего

Слайд 278 вариант
Имеется два вида корма I и II, содержащие питательные

вещества (витамины) S1 S2 и S3. Содержание числа единиц питательных

веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице:
 







Стоимость 1 кг корма I и II соответственно равна 4 и 6 ден. ед.
Необходимо составить дневной рацион, имеющий минимальную стоимость.
8 вариантИмеется два вида корма I и II, содержащие питательные вещества (витамины) S1 S2 и S3. Содержание

Слайд 289 вариант
При производстве двух видов продукции используется 4 типа

ресурсов. Норма расхода ресурсов на производство единицы продукции, общий объем

каждого ресурса заданы в таблице
 







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






9 вариант При производстве двух видов продукции используется 4 типа ресурсов. Норма расхода ресурсов на производство единицы

Слайд 2910 вариант
Фирма производит два безалкогольных напитка – «Лимонад» и

«Тоник».
Однако объем производства ограничен количеством основного ингредиента и производственной

мощностью имеющегося оборудования.
Для производства 1 л «Лимонада» требуется 0,02 ч работы оборудования, а для производства 1 л «Тоника» – 0,04 ч.
Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л «Лимонада» и «Тоника» соответственно.
Ежедневно в распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента.
Прибыль фирмы составляет 0,10 ден. ед. за 1 л «Лимонада» и 0,30 ден. ед. за 1 л «Тоника».
Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневной прибыли?






10 вариант Фирма производит два безалкогольных напитка – «Лимонад» и «Тоник». Однако объем производства ограничен количеством основного

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

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


Для правообладателей

Яндекс.Метрика