Линейное программирование (Графический метод. Симплексный метод) (стр. 4 )

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

При необходимости задачу на нахождение максимума целевой функции можно заменить задачей на минимум новой целевой функции, и наоборот, воспользовавшись следующим равенством min z= - max (-z).

Если дано неравенство вида , то необходимо ввести в левую часть неравенства дополнительную (балансовую) неотрицательную переменную : .

Каждая переменная задачи имеет определенный экономический смысл, в том числе и вводимые дополнительные переменные. Дополнительные переменные в задаче «об оптимальном использовании ресурсов» показывают количество неизрасходованного ресурса соответствующего вида. В задаче «о диете» эти переменные характеризуют объем потребления соответствующего вещества, превышающего норму. Таким образом, вводимые дополнительные переменные не могут принимать отрицательных значений.

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

найти минимум линейной функции

при условиях

Решение. Начнем с преобразования смешанной системы ограничений в систему уравнений. Первое ограничение является уравнением, поэтому не требует изменений. Необходимо перейти для второго и третьего ограничения от вида неравенства к виду уравнения. Для этого введем неотрицательные «балансовые» переменные и в левые части неравенств со знаками «плюс» или «минус» в зависимости от знака неравенства. Получим систему ограничений в следующем виде

Переход к задаче максимизации линейной функции осуществляется путем введения новой функции из равенства

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

найти максимум функции

при условиях

Вопросы:

1)  Приведите общую постановку задачи математического программирования?

2)  Приведите экономико-математическую модель задачи «об оптимальном использовании ресурсов», задачи «о диете».

3)  Какая форма задачи линейного программирования называется общей, стандартной, канонической? В чем заключаются сходства и различия этих форм?

4)  Какое решение задачи линейного программирования называется допустимым решением? Оптимальным решением?

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

Упражнения

Составить экономико-математическую модель задачи

1  На предприятии для производства двух видов продукции используется 2 вида ресурсов. Расход каждого вида ресурса на изготовление единицы каждого вида продукции, запасы каждого вида ресурсов, а также доходы от реализации единицы каждого вида продукции приведены в таблице 1.5.

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

Таблица 1.5 – Исходная информация задачи 1

Вид ресурса	Необходимое количество условных единиц ресурсов на единицу продукции	Запас ресурса
	2	1	8
	1	2	10
Доход от реализации единицы продукции	1	1

2  При откорме животных каждое животное должно ежедневно получить не менее 13 ед. питательного вещества А, не менее 18 ед. вещества В и не более 68 ед. витамина С. Эти питательные вещества содержат два вида корма. Содержание единиц питательного вещества в 1 кг каждого вида корма и цена приведены в таблице 1.6.

Таблица 1.6 – Исходная информация задачи 2

Питательное вещество	Вид корма	Минимальная суточная потребность в питательном веществе, усл. ед.
А	4	13	13
В	3	2	18
С	1	11	68
Стоимость 1кг корма	4	1

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

3  При производстве двух видов продукции и используются три вида сырья , , . Известны запасы каждого вида сырья: 40, 15 и 28. Для изготовления единицы продукции вида необходимо 3 ед. сырья , 2 ед. сырья вида и 4 ед. сырья вида . Производство единицы продукции вида требует затрат 5 ед. сырья вида , 1 ед. сырья вида и 1 ед. сырья вида . При реализации одной единицы продукции вида предприятие получает прибыль в 2 ден. ед, а при реализации одной единицы продукции вида прибыль составит 4 ден. ед. Требуется составить план выпуска продукции, при котором предприятие получит наибольшую прибыль.

4  Завод тяжелого машиностроения производит станки двух видов 3СБШ и 6СБШ. Для данного производства используется три вида сырья: металлопрокат в объеме 77 усл. ед., трубы в объеме 78 усл. ед, чугуны в объеме 54 усл. ед. На производство одного станка вида 3СБШ расходуется 1 усл. ед. металлопроката, 4 усл. ед. труб, 4 усл. ед. чугунов. Выпуск одного станка вида 6СБШ требует затрат металлопроката в количестве 7 усл. ед, труб в количестве 5 усл. ед. и 1 усл. ед. чугунов. Прибыль завода от реализации одного станка вида 3СБШ составит 3 ден. ед., а прибыль от реализации одного станка вида 6СБШ равна 4 ден. ед. Составит план производства станков указанного вида, который приносил бы заводу наибольшую прибыль.

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

5  ; .	6  ; .
7  ; .	8  ; .
9  ; .

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

2.1 Свойства основной задачи линейного программирования

Определение 1 Выпуклой линейной комбинацией произвольных точек Х1, Х2,…,Хn, принадлежащих евклидову пространству Еn , называется сумма , где и .