Ввод исходной информации

Готовим таблицу в Еxcel как показано на рис.2.1.

	А	В	С	D	E	F	G
	переменные	огранич.
	целые	xi1	xi2	xi3	лев.часть	знак	пр.часть
	х1j
	x2j
	x3j
	лев.часть
	знак
	пр.часть						баланс
	тарифы	xi1	xi2	xi3
	х1j
	x2j				ЦФ	напр
	x3j					мин

Рисунок 2.1. Исходные данные транспортной задачи

Ячейки В3: D5 (выделены синим цветом) предназначены для переменных, в ячейках G3: G5 содержатся ограничения по мощностям (наличие товара на складе), ячейки В8: D8 содержат ограничения по спросу, в ячейках В11: D13 находятся коэффициенты матрицы С={c_ij}.

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

 

 

Формулы для экранной формы транспортной задачи

Таблица 2

Объект математической модели	Выражение в Excel
Переменные задачи	В3: D5
Формула в целевой ячейке E13	=СУММПРОИЗВ(B3: D5; B11: D13)
Ограничения по строкам в ячейках E3, E4, E5	=СУММ(B3: D3) =СУММ(B4: D4) =СУММ(B5: D5)
Ограничения по столбцам в ячейках B6, C6, D6	=СУММ(B3: B5) =СУММ(C3: C5) =СУММ(D3: D5)
Суммарные запасы и потребности в ячейках G7, F8	=СУММ(G3: G5) =СУММ(B8: D8)

Дальнейшие действия (аналогично проведенным в работе 1) производятся в окне " Поиск решения", которое вызывается из меню " Сервис". Окно " Поиск решения" после ввода всех необходимых данных транспортной задачи представлено на рис.2.2.

Рисунок2.2. Окно " Поиск решения" транспортной задачи

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

Рисунок2.3. Экранная форма двухиндексной задачи (курсор в целевой ячейке Е13)

В рассмотренном примере суммарное наличие товара на всех складах совпадает с общей потребностью, поэтому в " Поиске решения" (рис.2.2) мы использовали знак равенстваB6: D6=B8: D8 (удовлетворить потребности) и E3: E5=G3: G5 (вывести весь товар) – такая транспортная задача называется закрытой. В случае избытка товара второе условие необходимо записывать со знаком ≤, тогда в результате решения у каких-то поставщиков останутся излишки товара. В случае дефицита товара первое условие необходимо записывать со знаком ≤, тогда в результате решения какие-то потребители окажутся частично неудовлетворенны (открытые задачи).

Задание 2.1. Компания «Стройгранит» производит добычу строительной щебенки и имеетна территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона дали заказ на поставку соответственно 300, 600, 650 и 500 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:

 

Карьер	Строительный объект
		а
	31 -а

Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными.

Значение неизвестного параметра а взять равным номеру варианта.

Рассмотрим еще один вид задач, сводящихся к ЗЛП – задачу о назначениях.

Задание 2.2. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:

Рабочие	Станки
С1	С2	С3	С4
Р1	2, 3	1, 9+ а /20	2, 2	2, 7
Р2	1, 8+ а /20	2, 2	2, 0	1, 8+ а /20
Р3	2, 5	2, 0	2, 2	3, 0
Р4	2, 0	2, 4	2, 4– а /20	2, 8

Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?

Значение неизвестного параметра а взять равным номеру варианта.

Обозначим за x_ij, i =1, 2, 3, 4; j =1, 2, 3, 4 - переменные, которые принимают значения 1, если i -й рабочий работает на j -м станке. Если данное условие не выполняется, то x_ij = 0. Целевая функция есть:

2, 3 x ₁₁+(1, 9+ а /20) x ₁₂+2, 2 x ₁₃+2, 7 x ₁₄+(1, 8+ а /20) x ₂₁+2, 2 x ₂₂+2 x ₂₃+(1, 8+ а /20) x ₂₄+

+2, 5 x ₃₁+2 x ₃₂+ 2, 2 x ₃₃+ 3 x ₃₄+ 2 x ₄₁+ 2, 4 x ₄₂+ (2, 4– а /20) x ₄₃+ 2, 8 x ₄₄→ min.

Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть

x ₁₁+ x ₁₂+ x ₁₃+ x ₁₄=1;

x ₂₁+ x ₂₂+ x ₂₃+ x ₂₄=1;

x ₃₁+ x ₃₂+ x ₃₃+ x ₃₄=1;

x ₄₁+ x ₄₂+ x ₄₃+ x ₄₄=1.

Кроме этого, каждый станок обслуживает только один рабочий:

x ₁₁+ x ₂₁+ x ₃₁+ x ₄₁=1;

x ₁₂+ x ₂₂+ x ₃₂+ x ₄₂=1;

x ₁₃+ x ₂₃+ x ₃₃+ x ₄₃=1;

x ₁₄+ x ₂₄+ x ₃₄+ x ₄₄=1.

Кроме того, все переменные должны быть целыми и неотрицательными: x_ij ≥ 0, x_ij – целые. (используйте 1.5).