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

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

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

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

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

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

Если целевая функция задачи подлежит минимизации, то для перехода к целевой функции, подлежащей максимизации, необходимо умножить исходную целевую функцию на (– 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.

12.

13.

14.

15.

16.

17.

18.

19.

20.

Контрольные вопросы

1. Сформулируйте задачу линейного программирования.

2. Дайте определение математической модели задачи и перечислите этапы ее построения.

3. Чем отличается допустимое решение задачи от оптимального?

4. Перечислите основные понятия линейного программирования.

5. Чем отличается общая задача линейного программирования от канонической?

6. Условия приведения задачи ЛП к стандартной (канонической) форме.

7. Дайте определение избыточной и остаточной переменных и поясните их физический смысл.

Лабораторная работа № 2

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Цель работы

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

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