Методические указания по изучению темы 10. Линейное программирование

Методические указания по изучению темы 10.

Линейное программирование

Линейное программирование – это направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными (неизвестными величинами) и линейным критерием.

Экстремальные задачи – это задачи, при решении которых находится экстремум функции, то есть ее максимум или минимум.

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

критерий должен быть единственным для данной задачи;

он должен количественно измеряться;

между различными неизвестными величинами, отыскиваемыми в задаче, зависимость должна быть линейной.

Задачи с нелинейными зависимостями между переменными являются объектом рассмотрения другого раздела математического программирования.

Формулировка задачи. Даны линейная функция

и система линейных ограничений

( j=1,2,…,n ),

где и - заданные постоянные величины.

Найти такие неотрицательные значения , которые удовлетворяют системе ограничений и доставляют линейной функции, называемой целевой, максимальное (минимальное) значение.

Графический метод решения задач линейного программирования. Этим методом решаются задачи, в которых целевая функция является функцией двух переменных

.

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

Каждое уравнение ограничивающих условий определяет прямую на плоскости. При этом данная прямая делит плоскость на две полуплоскости и описывает множество точек

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

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

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

Таким образом, оптимальное решение (оптимум) достигается в вершинах многоугольника области допустимых значений. Определив по графику координаты всех вершин, их подставляют в целевую функцию и получают различные значения F(x). Координаты вершин можно также определить, решив систему уравнений прямых, пересекающихся в данной вершине.

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

Методические указания к выполнению задания 14

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

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

Для перевозки контейнеров (К), посылок (П) и мешков (М) используют автомашины типа А и Б. Определите необходимое количество автомашин типа А и Б, если известны емкость машины за один рейс, необходимое количество перевозимых контейнеров, посылок и мешков.

Исходные данные представлены в таблице.

Тип машин	Емкость машин за один рейс	Количество машин на базе	Затраты на перевозку за один рейс, руб.
мешки ( М )	посылки ( П )	контейнеры ( К )
А Б	40 110	90 -	12 4	5 12	2,5 1,4
Общее кол. г рузов	192	240	90

Решение. Введем переменные. Пусть - это количество машин типа А, необходимое для перевозки грузов, - это количество машин типа Б. Тогда исходя из условий задачи запишем их математическую форму:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

Требуется найти такие значения х1 и х2 , чтобы затраты на перевозку всех мешков, посылок и контейнеров были минимальными, т. е.

(8)

Выражение с 1 по 8 – это есть искомая экономико-математическая модель.

Выражение с 1 по 5 – это ограничивающие условия (искусственные ограничения).

Выражения 6 и 7 – это требования неотрицательности переменных (естественные ограничения).

Выражение 8 – это функция цели min, которой нужно удовлетворить по условию задачи.

Для решения задачи преобразуем неравенство с 1 по 5 в уравнения.

Будем считать, что неиспользованный ресурс = 0, поэтому не будем вводить дополнительные переменные.

(1)

(2)

(3)

(4)

(5)

По каждому уравнению можно построить прямую.

(3)

Определим координаты двух точек, по которым можно построить прямую.

Примем х1=0, тогда х2=4, а если х2=0, то х1=11.

(4)

при х2=0, х1=2.

(5)

при х1=0, х2=12, при х2=0, х1=4.

Построим ОДР и обозначим вершины.

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

, соответствующих прямым l1 и l3 .

Вершины ОДР имеют следующие координаты: А(2; 12); Б(5; 12); В(5; ); Г(; Д(2; 6).

Для каждой точки вычисляем значения целевой функции :

.

Обратим внимание, что координаты точек В и Г не являются целыми числами, что противоречит физическому смыслу задачи (координаты точек – это количества машин каждого вида, используемых для перевозки грузов).

Если бы координаты всех вершин ОДР были целочисленными, то решением задачи были бы координаты той вершины ОДР, в которой F(x1; х2) принимает наименьшее значение.

Но в нашем случае целевая функция принимает наименьшее значение в вершине Г с нецелочисленными координатами. Для решения задачи необходимо вычислить функцию

F(x1; х2) в целочисленных точках, ближайших к точке Г, и выбрать ту, в которой целевая функция принимает наименьшее значение. Это точка (3; 3), где F(3; 3) = 11,7 .

Следовательно, для перевозки всех мешков, посылок и контейнеров необходимо использовать 3 автомобиля типа А и 3 автомобиля типа Б.

x2

 

12_ А(2; 12) Б(5; 12) l2

_

 

10_ l5

_

8_ ОД Р l1

_

 

6_ Д(2; 6)

 

_

4

 

_

В(5; 22/11)

2_ Г(31/29;226/29)

l4 l3

_

| | | | | | | | | | |

x1