Математические методы в экономике
Главная | Графический метод решения задач линейного программирования | Регистрация | Вход
 
Пятница, 24.11.2017, 23:04
Приветствую Вас Гость
Главное меню
Статистика
Форма входа

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

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

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

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

Областью решений линейного неравенства ai1x1 + ai2x2 ≤ bi является одна из двух полуплоскостей, на которые прямая ai1x1 + ai2x2 = 0, соответствующая данному неравенству, делит всю координатную плоскость.

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

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

Для нахождения среди допустимых решений оптимального решения используют линии уровня и опорные прямые.

Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня в общем случае имеет вид c1x1 + c2x2 = l, где l = const. Все линии уровня параллельны между собой. Их нормаль n = (c1, c2).

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

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

Алгоритм нахождения решения задачи

1. Строят прямые, уравнения которых получаются в результате замены в системе ограничений знаков неравенств на значки точных равенств.

2. Находятся полуплоскости, определяемые каждым из ограничений задачи.

3. Находят многоугольник решений.

4. Строят вектор C = (c1, c2).

5. Строят прямую c1x1 + c2x2 = h, проходящую через многоугольник решений.

6. Передвигают прямую c1x1 + c2x2 = h в направлении вектора C, в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.

7. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

Задача об использовании ресурсов

Для изготовления двух видов продукции P1 и P2 используют четыре вида ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице (цифры условные).

Вид ресурса Запас ресурсов Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
P1 P2
S1 18 1 3
S2 16 2 1
S3 5 - 1
S4 21 3 -

Прибыль, получаемая от единицы продукции P1 и P2, ˗˗ соответственно 2 и 3 рубля.

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

Решение

Задача составления рациона

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

Питательное вещество (витамин) Необходимый минимум питательных веществ Число единиц питательных веществ в 1 кг корма
I II
S1 18 3 1
S2 16 1 2
S3 5 1 6

Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб.

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

Решение


Copyright MyCorp © 2017Бесплатный конструктор сайтов - uCoz