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

Примеры выполнения заданий

Задача 3.

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

Графический метод решения задач линейного программирования - student2.ru

при ограничениях:

Графический метод решения задач линейного программирования - student2.ru

Решение.

Изобразим многоугольник решений на рис. 2. Очевидно, что при Графический метод решения задач линейного программирования - student2.ru линия уровня Графический метод решения задач линейного программирования - student2.ru проходит через начало координат (строить ее не обязательно). Зададим, например, Графический метод решения задач линейного программирования - student2.ru и построим линию уровня Графический метод решения задач линейного программирования - student2.ru . Ее расположение указывает на направление возрастания линейной функции (вектор Графический метод решения задач линейного программирования - student2.ru ). Так как рассматриваемая задача — на отыскание максимума, то оптимальное решение − в угловой точке Графический метод решения задач линейного программирования - student2.ru , находящейся на пересечении прямых I и II, т.е. координаты точки Графический метод решения задач линейного программирования - student2.ru

определяются решением системы уравнений

Графический метод решения задач линейного программирования - student2.ru откуда Графический метод решения задач линейного программирования - student2.ru , т.е. Графический метод решения задач линейного программирования - student2.ru .

Графический метод решения задач линейного программирования - student2.ru

Рис. 2.

Максимум (максимальное значение) линейной функции равен Графический метод решения задач линейного программирования - student2.ru Графический метод решения задач линейного программирования - student2.ru .

Итак, Графический метод решения задач линейного программирования - student2.ru при оптимальном решении Графический метод решения задач линейного программирования - student2.ru , т.е. максимальная прибыль в 24 руб. может быть достигнута при производстве 6 единиц продукции Графический метод решения задач линейного программирования - student2.ru и 4 единиц продукции Графический метод решения задач линейного программирования - student2.ru .

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

Задание к практическому занятию:

Базовый уровень:

В заданиях 1− 3 составить экономико-математические модели.

Задание 1. Для производства двух видов изделий Графический метод решения задач линейного программирования - student2.ru и Графический метод решения задач линейного программирования - student2.ru предприятие использует три вида сырья. Другие условия задачи приведены в таблице.

Вид сырья Нормы расхода сырья на одно изделие, кг Общее количество сырья, кг
Графический метод решения задач линейного программирования - student2.ru Графический метод решения задач линейного программирования - student2.ru
I
II
III
Прибыль от реализации одного изделия, ден.ед.  

Составить такой план выпуска продукции, при котором при­быль предприятия от реализации продукции будет максимальной при условии, что изделий Графический метод решения задач линейного программирования - student2.ru надо выпустить не менее, чем изде­лий Графический метод решения задач линейного программирования - student2.ru .

Задание 2.Рацион для питания животных на ферме состоит из двух видов кормов I и II. Один килограмм корма I стоит 70 ден.ед. и содержит: 0,5 ед. жиров, 4 ед. белков, 1 ед. углеводов, 1 ед. нитратов. Один килограмм корма II стоит 16 ден.ед. и содержит 3 ед. жиров, 6 ед. белков, 4 ед. углеводов, 3 ед. нитратов.

Составить наиболее дешевый рацион питания, обеспечиваю­щий жиров не менее 9 ед., белков не менее 5 ед., углеводов не менее 4 ед., нитратов не более 11 ед.

Задание 3.На двух автоматических линиях выпускают аппараты трех типов. Другие условия задачи приведены в таблице.

Тип аппарата Производительность работы линий, шт. в сутки Затраты на работу линий, ден.ед. в сутки План, шт.
   
Графический метод решения задач линейного программирования - student2.ru Графический метод решения задач линейного программирования - student2.ru Графический метод решения задач линейного программирования - student2.ru

Составить такой план загрузки станков, чтобы затраты были минимальными, а задание выполнено не более чем за 10 суток.

Повышенный уровень:

Задание 4.

Найти опорное решение задачи линейного программирования вида Графический метод решения задач линейного программирования - student2.ru и соответствующее допустимое значение целевой функции Графический метод решения задач линейного программирования - student2.ru :

Графический метод решения задач линейного программирования - student2.ru

Ответ: Графический метод решения задач линейного программирования - student2.ru 4

Задание 5.

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

Графический метод решения задач линейного программирования - student2.ru и соответствующие допустимые значения целевой функции Графический метод решения задач линейного программирования - student2.ru :

Графический метод решения задач линейного программирования - student2.ru

Ответ: Графический метод решения задач линейного программирования - student2.ru 2

Задание 6.

Найти опорное решение задачи линейного программирования вида Графический метод решения задач линейного программирования - student2.ru и соответствующее допустимое значение целевой функции Графический метод решения задач линейного программирования - student2.ru :

Графический метод решения задач линейного программирования - student2.ru

Ответ: Графический метод решения задач линейного программирования - student2.ru 3

Задание 7.

Решить графическим методом задачи с двумя переменными (табл. 1)

Таблица 1. Варианты задания 7

Вариант Задача Вариант Задача
Z(X)=2x1+4x2®max, Графический метод решения задач линейного программирования - student2.ru x1³0, x2³0 Z(X)=-3x1-x2®min, Графический метод решения задач линейного программирования - student2.ru x1³0, x2³0
Z(X)=15x1+10x2®max, Графический метод решения задач линейного программирования - student2.ru x1³0, x2³0 Z(X)=2x1+3x2®max, Графический метод решения задач линейного программирования - student2.ru x1³0
Z(X)=3x1+2x2®max, Графический метод решения задач линейного программирования - student2.ru x1³0, x2³0 Z(X)=4x1+6x2®max, Графический метод решения задач линейного программирования - student2.ru  

Продолжение таблицы 1. Варианты задания 7

Z(X)=2x1+5x2®min, Графический метод решения задач линейного программирования - student2.ru x1³0, x2³0 Z(X)=-x1+4x2®min, Графический метод решения задач линейного программирования - student2.ru x2³0
Z(X)=2x1-x2®max, Графический метод решения задач линейного программирования - student2.ru x1³0, x2³0 Z(X)=x1+4x2®min, Графический метод решения задач линейного программирования - student2.ru x1³0, x2³0

Задание 8. Решить графическим методом задачи с Графический метод решения задач линейного программирования - student2.ru переменными (табл. 2).

Таблица 2. Варианты задания 8

Вариант Задача Вариант Задача
Z(X)=2x1+8x2+3x3+4x4® min, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4 Z(X)=2x1+6x2+x3+x4®max, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4
Z(X)=2x1+3x2-x3+4x4®min, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4 Z(X)=2x1+5x2+x3+x4®max, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4
Z(X)=4x1+13x2+3x3+6x4®min, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4 Z(X)=9x1+2x2+4x3-8x4®max, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4
Z(X)=x1+x2+3x3+4x4®min, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4 Z(X)=x1-2x2-x3+3x4®max, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4
Z(X)=11x2+x3+4x4®min, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4 Z(X)=2x1+x2-x3-2x4®min, Графический метод решения задач линейного программирования - student2.ru xj³0, j=1,2,3,4

Вопросы для самостоятельной работы

Базовый уровень:

1. Что называется экономико-математической моделью?

2. Перечислить основные этапы экономико-математического моделирования.

3. Что называется целевой функцией?

4. Сформулируйте общую постановку задачи линейного программирования.

Повышенный уровень:

5. В чем суть принципа оптимальности в планировании и управлении?

6. В чем заключается геометрическая интерпретация задачи линейного программирования?

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

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

9. Какое направление для целевой функции указывает ее градиент?

10. Когда применяется графический метод ЗЛП?

Наши рекомендации