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

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

 

Вариант 10.

Задание 1.

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

 

_{Решение.}

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

 

I.

	0	3
	6	0

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

 

II.

	0	10
	5	0

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

 

III.

	0	6
	6	0

Решением данного уравнения  является прямая III.

Кроме того, по условию  ,

Таким образом решение  системы  , находится в I четверти координатной плоскости, заключено между прямыми I и II, и при этом принадлежит прямой III, всем этим условиям соответствует отрезок АВ.

Координаты точки В  мы нашли ранее В(6;0), координаты точки  А находятся решением системы:   А(2;4)

A

 

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

(3;2), затем построим перпендикулярно  вектору прямую, проходящую через начало координат,  перемещая данную прямую в направлении вектора заметим что она входит в область определения в точке А (на рисунке прямая а), это минимум данной функции. При дальнейшем перемещении прямой видно, что она выходит из области определения в точке В (на рисунке прямая b), это максимум данной функции.

 

 

 

 

 

 

 

2. Симплексный метод

 

Задание 2.

Предположим, что в производстве двух видов продукции А и В  принимают участие три предприятия. При этом на изготовление единицы  изделия А первое предприятие  тратит 5 ч, второе предприятие – 9 ч, третье предприятие – 10 ч. На изготовление единицы изделия В первое предприятие  тратит 7 ч, второе предприятие – 9 ч, третье предприятие – 8 ч. На производство всех изделий первое предприятие  может затратить не более чем 343 ч, второе предприятие – 587 ч, третье предприятие – 587 ч. От реализации единицы готовой продукции вида А прибыль составляет 11 руб., а вида В – 7 руб.

Определить максимальную прибыль от реализации всей продукции  видов А и В. Решить задачу симплекс-методом. Дать геометрическую интерпретацию  математической формулировки.

 

Решение.

Представим данные этой задачи в виде таблицы:

	Изделие А ч.	Изделие В ч.	Допустимые затраты ч.
I предприятие	5	7	343
II предприятие	9	9	587
III предприятие	10	8	587
Прибыль от реализации руб.	11	7

  Пусть количество изделий вида А будет , а количество изделий вида В – , тогда функция прибыли будет иметь вид:

 Составим систему  ограничений.

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

 

Составим симплекс-таблицу:

 

	343	5	7	1	0	0	343/5=68.6
	587	9	9	0	1	0	587/9=65.2
	587	10	8	0	0	1	587/10=58.7
F	0	-11	-7	0	0	0

Разрешающий столбец  , разрешающая строка .

Получим таблицу следующего вида:

		0
		0
	58,7	1	0,8	0	0	0,1
F		0

 После вычислений получим:

	49,5	0	3	0	0	-0,5
	58,7	0	1,8	0	0	-0,9
	58,7	1	0,8	0	0	0,1
F	645,7	0	1,8	0	0	1,1

 

В данной таблице нижняя строка F не содержит отрицательных значений, а значит мы пришли к оптимальному решению задачи. Причем наиболее выгодным оказалось производство изделия А, а на первом и втором предприятиях образовались излишки рабочего времени, соответственно 49,5 и 58,7 часов. Для увеличения объемов выпуска необходимо повысить эффективность третьего предприятия. 

X (58.7; 0; 49.5; 58.7; 0)

 

 

 

 

 

 

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

 

I.

	0	68.6
	49	0

II.

	0	65.2
	65.2	0

 

В

III.

	0	а b 58.7
	73.4	0

 

Область значений данной системы  равенств ограничена отрезком координатной прямой y от 0 до 49, отрезком координатной прямой x от 0 до 58,7, отрезком прямой I от пересечения с координатной прямой y до пересечения с прямой III и прямой III от пересечения с прямой I до пересечения с координатной прямой x.

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

(11; 7), затем построим перпендикулярно  вектору прямую, проходящую через  начало координат,  перемещая  данную прямую в направлении  вектора  заметим что она входит в область определения в точке 0 (на рисунке прямая а), это минимум данной функции. При дальнейшем перемещении прямой видно, что она выходит из области определения в точке В (на рисунке прямая b), это максимум данной функции.

 

 

 

 

 

 

 

_{3. Транспортная задача.}

_{Задание 3. Имеются  три пункта поставки однородного груза} 

_{и четыре пункта                                      потребления этого груза. На пунктах}

                     _{находится груз  соответственно в  количестве 300, 320 и  380 т. В пункты                                    требуется доставить  соответственно 250, 200, 290 и 260 т груза.  Расстояние между  пунктами поставки  и пунктами потребления  приведено в следующей  таблице:}

 

Пункты  отправления	Пункты  назначения				Запасы
	1	4	5	11	300
	12	8	3	14	320
	10	15	7	9	380
Потребности	250	200	290	260	1000

 

_{Решение:}

_{Данная  задача имеет закрытую модель, так как суммарная мощность поставщиков равна суммарному спросу потребителей. И действительно 300+320+380=1000 и 250+200+290+260=1000.}

_{Для  решения этой задачи необходимо произвести первоначальное распределение  поставок, воспользуемся  для этого правилом учета наименьших затрат,  а таблицу перегруппируем.} 

Пункты  отправления	Мощности  поставщиков	Пункты  назначения и их спрос
		250	200	290	260
	300	1	4	5	11
	320	12	8	3	14
	380	10	15	7	9