Мастерская программиста Гирича Семёна Николаевича
Решение задач линейного программирования

2.3. Пример решения задачи ЛП графическим методом

Задача:

Рацион для питания животных на ферме состоит из двух видов кормов 1 и 2.
Один килограмм корма 1 стоит 80 р. и содержит 1 ед. жиров, 3 ед. белков,
1 ед. углеводов, 2 ед. нитратов. Один килограмм корма 2 стоит 10 р. и
содержит 3 ед. жиров, 1 ед. белков, 8 ед. углеводов, 4 ед. нитратов.
Составить наиболее дешевый рацион питания при условии, что:
Жиров .....……. не менее 6 ед.
Белков .....….... не менее 9 ед.
Углеводов ..…. не менее 8 ед.

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

Целевая функция:
S min = 80*x1+10*x2

Система ограничений:
x1+3*x2>=6
3*x1+x2>=9
x1+8*x2>=8
2*x1+4*x2<=16

x1,x2 >=0; - условие неотрицательности переменных.


Решение задачи с использованием графического симплекс-метода.

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

Чтобы построить прямую нужно знать координаты двух точек.
Координаты точек прямых соотствующих неравенствам:

Неравенство    X1 Y1 X2 Y2
x1+3*x2>=6   6 0 0 2
3*x1+x2>=9   3 0 0 9
x1+8*x2>=8   8 0 0 1
2*x1+4*x2<=16   8 0 0 4

Построим вектор целевой функции S(80;10).

Система координат с областью допустимых решений и вектором целевой функции приведена на рис.1.

График области допустимых решений.

Рис.1:График области допустимых решений.

Как видно из графика, минимальной вершиной области допустимых значений будет вершина (2;3).

В данной вершине значение целевой функции равно:
S min = 80*2+10*3
И в результате:
S min = 190

Задача решена.


Далее: 3. Решение методом симплекс-таблиц

Вернуться в Начало

© 2011 Семён Гирич,
Система Orphus: Выделите текст с ошибкой и нажмите [Ctrl] + [Enter]
Назад    Вверх