Построение области допустимых решений задачи линейного программирования

Цель работы: закрепить представление об области допустимых решений задачи линейного программирования как о выпуклом многоугольнике и приоб­рести навыки построения области допустимых решений.

Теоретическое обоснование

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

Для построения области допустимых решений:

1. Строят множество решений каждого неравенства.

1.1. По точкам пересечения с осями координат строят границу полуплос­кости каждого неравенства. Это прямая, значения коэффициента и свободного члена которой соответственно равны значениям коэффициента и свободного члена неравенства.

Для данного примера это прямые

Для расчета точки пересечения прямой с осью 0X1 значение переменной х2 принимается равным нулю. Для расчета точки пересечения прямой с осью ОХ2 значение переменной xl принимается равным нулю. Пример расчета ко­ординат точек пересечения границ полуплоскостей ОДР с осями координат приведен в табл. 2.

Таблица 2.

Уравнение границы полу­плоскости	Координаты точек пересе­чения границ полуплоско­стей с осью 0X2		Координаты точек пересе­чения границ полуплоско­стей с осью ОХ 1
	xl	х2	xl	х2
		х2=42/2=21	х1=42/1,5=28	х2=0
		х2=60/2=30	х1=0/3=20	х2=0
		х2=200/5=40	xl= 200/5=40	х2=0
xl = 18		х2=18/0=∞;	xl = 18/1=18	х2=0

1.2. Определяют искомые полуплоскости, содержащие множество реше­ний каждого неравенства.

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

Удобно взять точку (10, 10), координаты которой необходимо подставить в каждое неравенство системы неравенств. Если неравенство выполняется в этой точке (знак неравенства остается прежним), то оно выполняется и во всех точках полуплоскости, содержащей точку (10, 10):

- неравенство выполняется в точке (10,10):

- неравенство выполняется в точке (10,10);

- неравенство выполняется в точке (10,10);

10 < 18 - неравенство выполняется в точке (10,10).

Содержащую множество решений неравенства полуплоскость заштрихо­вывают.

2. Находят область допустимых решений.

Фигура, которая образовалась в результате пересечения всех заштрихо­ванных полуплоскостей, является областью допустимых решений (ОДР). Если хотя бы одна заштрихованная полуплоскость не имеет ни одной общей точки с остальными, то такая система неравенств будет несовместной, а ЗЛП не будет иметь решения.

—•—Ткань

◊Трудоемкость

̱ ̱ ̱ ̱ ̱ Накладные расходы

̶ ̶Спрос

—*—

—•—

― ЦФ

―○― ТО

Рис. 1

Пересечением всех заштрихованных полуплоскостей на рис. 1 является выпуклый многоугольник ABCDE. Это и есть искомая область допустимых решений.

Ход выполнения

1. В поле EXCEL заносим расширенную матрицу ЗЛП (табл. 3).

Каждый коэффициент расширенной матрицы заносится в числовом фор­мате в отдельную ячейку.

Условия неотрицательности переменных также должны быть представлены в расширенной матрице.

Необходимо достаточно точно и понятно сделать подписи каждого огра­ничения и каждой переменной. Расширенную матрицу удобно представить в виде табл. 3.

Ячейки, содержащие длинные названия и предложения, должны быть от­форматированы. Подлежащие форматированию ячейки выделяют черным цве­том удержанием левой кнопкой мыши, затем последовательно выполняют сле­дующие действия: в меню EXCEL «Формат» выбирают «Ячейки», находят за­кладку «Выравнивание»,ставят флажок напротив «переносить по словам». В отформатированных таким способом ячейках «длинный» текст будет перено­ситься на следующую строку таблицы так, как в ячейке А4(табл. 3).

	А	В	С	D
1		Юбки (XI)	Брюки (Х2)	Запас ресурсов
2	Ткань	1,5	2	42
3	Трудоемкость	3	2	60
4	Накладные расходы	5	5	200
5	Спрос	1		18
6		1		0
7			1	0

2. Рассчитывают координаты точек пересечения с осями ОХ1 и ОХ2.

Каждая прямая имеет две точки пересечения с осями координат: одну с осью ОХ1 и одну с осью ОХ2. Соответственно у каждой точки имеется две ко­ординаты. Поскольку имеется две точки пересечения, го всего координат должно быть четыре.

Для построения прямой в графическом редакторе EXEL расположите в соседних ячейках одноименные координаты точек пересечения с осями OXI иОХ2.Справа от построенной расширенной матрицы выделите по два столбца с одноименными координатами (табл. 4). В столбцах Е и G табл. 4 будут рас­считываться координаты точки пересечения прямой с осью ОХ2, а в столбцах Fи Н - координаты точки пересечения прямой с осью ОХ1.

Для создания шапки при необходимости используйте объединение ячеек.

Используйте опцию «Выравнивание» для того, чтобы отрегулировать расположение надписей в табл. 4.

Таблица 4

	А	В	С	D	Е	F	G	Н
1					Координаты		Координаты
					на оси	0X1	на оси	ОХ2
2		Юбки	Брюки	Запас		Х1	Х2	Х2=0
		( )	(Х2)	ресур-
				сов
3	Ткань	1,5	2	42	0	=D3/	=D3/	0
						ВЗ	сз
4	Трудоем-	3	2	60	0			0
	кость
5	Накладные	5	5	200	0			0
	расходы
6	Спрос	1		18	18	=D6/	лю-	0
						В6	бое
7		1		0	0			0
8			1	0	0			0

Рассчитайте с помощью формул координаты пересечения первой прямой с осями ОХ1 и ОХ2. Запишите формулы в ненулевые ячейки, предназначенныедля расчета координат. Затем с помощью копирования размножьте формулы по остальным ячейкам.

При размножении формул недоступными для операций в EXCEL оста­нутся ячейки, содержащие значение #ДЕЛ/0!. Деление на ноль встречается при расчете координат для прямых, параллельных осям координат. Для построения таких прямых в графиках EXCEL существует два способа: вручную мышкой «растянуть» прямую в нужное положение или ввести в ячейку любое числовое значение, как в ячейке G6 (табл.4). В первом случае необходимо щелкнуть мышкой по построенной прямой. Напрямой появятся маркеры. Вторым щелч­ком мышки необходимо зацепить нужный маркер и «растянуть» прямую.

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

3. По сформированным данным строят график ОДР в диаграмме EXCEL.

На первом шаге построения открывают диаграмму EXCEL и выбирают из всех видов диаграмм «Точечную», а именно, одну из трех представленных в примере точечных диаграмм с соединительными линиями между точками.

На втором шаге построения удаляют из окна «Диапазон» (закладка «Диапазон данных») все автоматически набранные EXCEL диапазоны. В за­кладке «Ряды» нажимают кнопку «Добавить». В появившемся окне «Имя» с помощью ссылки устанавливают адрес ячейки с названием первого ограниче­ния (табл.5). В окне «Значения X» с помощью ссылки устанавливают адреса ячеек с координатами, которые лежат на оси ОХ1. В окне «Значения У» с по­мощью ссылки устанавливают значения ячеек с координатами ОХ2. Для созда­ния ссылки достаточно сначала щелкнуть мышкой по диалоговому окну, затем по нужной ячейке поля EXCEL.

Таблица 5

Имя	=Лист1!$АЗ
Значения X	ссылка
Значения У	ссылка

На третьем шаге построения диаграммы указывают название диаграммы и подписывают оси 0X1 и 0X2, размечают основные и промежуточные линии сетки и указывают место размещения легенды.

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

На этом построение ОДР в графическом редакторе EXCEL завершается.

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