Приведение задач ЛП к стандартной форме

⇐ Назад

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

Для большинства методов решения задач ЛП требуется предварительно привести задачу к стандартной (канонической, нормальной) форме. Задача (или ее математическая модель) представлена в стандартной форме, если она соответствует следующим условиям:

· Целевая функция подлежит максимизации;

· Все ограничения имеют вид равенств;

· На все переменные накладываются ограничения неотрицательности.

Если целевая функция задачи подлежит минимизации, то для перехода к целевой функции, подлежащей максимизации, необходимо умножить исходную целевую функцию на (– 1). Доказано, что максимальное значение любой функции Е всегда равно минимальному значению функции (– Е), взятому с обратным знаком.

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

Если на какую-либо переменную накладывается ограничение неотрицательности, то она заменяется на разность двух переменных, каждая из которых должна быть неотрицательной. Таким образом, если некоторая переменная x_j по своему физическому смыслу может принимать как положительные, так и отрицательные значения, то во всех ограничениях и в целевой функции ее следует заменить на разность двух переменных: x^’_j – x^”_j. На эти переменные накладываются ограничения неотрицательности: x^’_j 0, x^”_j 0.

Приведем к стандартной форме задачу из примера 1.1. Из ограничений «больше или равно» необходимо вычесть избыточные переменные, к ограничению «меньше или равно» - прибавить остаточную переменную. Целевая функция задачи подлежит максимизации, и на все переменные накладывается ограничение неотрицательности; поэтому никаких других преобразований не требуется. Математическая модель задачи в стандартной форме будет иметь следующий вид:

x₁– x₃ =200

x₂– x₄ =100

0,5x₁+1,2x₂+x₅=600

x₁0; x₂0

Е=25x₁+40x₂→ max

Здесь переменные x₃, x₄– избыточные, x₅ – остаточная.

Примечание. Все переменные, которые вводятся в математическую модель для ее приведения к стандартной форме, имеют физический смысл. Так, в рассмотренном примере переменные x₃и x₄обозначают количество кислот, которое будет выпущено сверх государственного заказа. Переменная x₅обозначает, насколько количество опасных отходов, образующихся при производстве кислот, будет меньше максимально допустимой величины (600 т).

Приведем к стандартной форме задачу из примера 1.2. В ней имеются три ограничения «больше или равно». В каждое из них необходимо ввести избыточную переменную. Целевая функция задачи подлежит минимизации, ее необходимо умножить на (– 1), чтобы перейти к целевой функции, подлежащей максимизации. Математическая модель задачи в стандартной форме будет иметь следующий вид:

x₁– x₃ =200

x₂– x₄ =100

25Х₁+40x₂–x₅=20000

x₁0; x₂0

–Е=–0,5x₁–1,2x₂→ max.

Порядок выполнения работ

1. Изучить теоретическую часть.

2. Составить математическую модель задачи.

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

4. Привести математическую модель задачи к каноническому виду.

Варианты заданий для лабораторной работы № 1

Построить математическую модель

1. Имеется производство по изготовлению двух видов продукции А и В при ограниченном объеме материалов трех сортов, из которых производится продукция. Исходные данные приведены в таблице.

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

2. Продукция может производиться двумя технологическими способами Т₁ и Т₂. На производство продукции затрачиваются ресурсы трех видов R₁; R₂; R₃, запасы которых равны: 15; 18; 8. Расход ресурсов на производство всей продукции по первому технологическому способу составляет 2; 4; 0, а по второму - 3; 2; 2. Выход продукции по способу Т₁ равняется 10 единицам, по Т₂ - 8. Определить с какой интенсивностью нужно применять каждый тех. способ, чтобы при этих запасах иметь максимум продукции.

3. Из двух сортов бензина составляют две смеси А и Б. Смесь А содержит 60% бензина первого сорта и 40% - второго. Смесь Б содержит 80% бензина первого сорта, 20% - второго. Продажная цена 1 кг смеси А - 10 к.; смеси Б - 12 к. Составить план образования смесей, при котором будет получен максимальный доход, если в наличии 50 т бензина 1-го сорта и 30 т - второго.

4. Предприятие выпускает два вида изделий П₁ и П₂, на изготовление которых идет 3 вида сырья: S₁; S₂; S₃, запасы которых равны 200, 110, 120 ед. Расход сырья на 1000 ед. продукции составляет: S₁ - 20; 10; S₂ - 20; 5; S₃- 10; 10. Оптовая цена за 1000 шт. изделий составляет: 15; 17 тыс. рублей. Себестоимость производства 1000 шт. изделий составляет 12 и 15 тыс. рублей. Составить план выпуска продукции, обеспечивающий максимальную прибыль, предполагая, что сбыт неограничен.

5. Предприятие имеет три производственных фактора в количестве 6; 5; 2 тыс. единиц и может организовать производство двумя различными способами. Расход производственных факторов по первому способу производства составляет 1; 1; 3 тыс. единиц, по второму - 3; 1; 2 тыс. По первому способу предприятие выпускает в месяц 3 тыс. изделий, в по второму - 2 тыс. изделий. Сколько времени предприятие должно работать каждым способом, чтобы получить максимум продукции?

6. На каждую автоколонну из 10 машин, направленных для вывоза груза из района А, выделяется 4 передвижных мастерских, 3 машины тех помощи, 2 мотоцикла. На такую же автоколонну для вывоза груза из района В выделяется 3 передвижные мастерские, 1 машина тех помощи. Одна колонна из района А вывозит 2 тыс. тонн груза, из района Б - 1 тыс. тонн груза. Какое количество автоколонн следует направить в каждый район, чтобы обеспечить максимальный вывоз груза, если имеется 200 машин, 20 авторемонтных мастерских, 10 машин тех помощи, 16 мотоциклов?

7. Предприятие выпускает два вида изделий П₁ и П₂, используя 4 группы станков (А, Б, В, Г), фонды рабочего времени которых (час.) составляют 10; 30; 20; 12 часов. На производство одного изделия П₁ каждая группа станков тратит (соответственно): 4; 0; 1; 3 ч. Для П₂ - 2; 3; 2; 2 ч. Прибыль от реализации каждого изделия П₁ равна 2 рубля; П₂ - 3 рубля. Найти план производства, дающий максимальную прибыль.

8. В животноводческом совхозе на производство одного центнера молока тратится 25 рублей, из них на трудовые затраты - 10 рублей, на материальные - 15 рублей; производство 1 центнера мяса обходится в 180 рублей, из которых 100 рублей - трудовые затраты, 80 рублей – материальные. Государственные закупочные цены за 1 центнер молока - 35 рублей, а за 1 центнер мяса - 200 рублей. Определить оптимальный план производства молока и мяса, если на животноводство выделено 190000 рублей. Фонд зарплаты - 100000 рублей, остальное - на оборудование.

9. Из Минска в Гродно необходимо перевезти оборудование трех типов. I типа - 84 ед.; II - 80 ед.; III - 150 ед., для чего используют два вида транспорта А и Б. Количество оборудования каждого типа на транспорт А составляет: 3; 4; 3 ед., - транспорт Б: 2; 1; 13 ед. Затраты на перевозку транспортом А равны 8 ед., Б - 12 ед. Составить такой план перевозок, чтобы транспортные расходы были минимальными.

10. Трикотажная фабрика производит свитеры и кофточки, используя шерсть, силон и нитрон, запасы которых соответственно равны 900; 400; 300 кг. Количество каждой пряжи на изготовление 10 свитеров составляет: 4; 2; 1 кг, а 10 кофточек: 2; 1; 1 кг. Прибыль от реализации 10 ед. продукции: 6 и 5 рублей. Найти план выпуска, максимизирующий прибыль.

11.