Формирование элементов математической модели

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

Транспортная задача.

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

Имеется m пунктов отправления A1, A2, . . . , Am, в которых сосредоточены запасы однородных грузов в количестве соответственно a1, a2, . . . , am единиц. Имеетсяn пунктов назначения В1, В2, . . . , Вn, подавших заявки соответственно на b1, b2, . . . , bn единиц груза. Если сумма всех заявок равна сумме всех запасов

то задача называется задачей закрытого типа. Известны стоимости Сij перевозки единицы груза от каждого пункта отправления Ai до каждого пункта назначения Bj. Все числа cij образующие прямоугольную матрицу, заданы:

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

Обозначим xij - количество единиц груза, отправляемого из пункта Ai в пункт назначения Bj . Неотрицательные переменные xij можно записать в виде матрицы

Эти неотрицательные переменные должны удовлетворять следующим условиям:

1) Суммарное количество груза, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте.

2) Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно заявке, поданной данным пунктом.

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

3) Суммарная стоимость всех перевозок должна быть минимальной:

В силу особой структуры ТЗ все операции по нахождению оптимального плана сводятся к манипуляциям непосредственно с таблицей. Транспортная таблица состоит из m строк и n столбцов. В верхнем левом углу каждой клетки будем указывать стоимость Cij перевозки единицы груза из Аi в Вj , а в правом нижнем углу помещаем перевозку xij.

Заказы Запасы		B₁		B₂		…	B_n
		b₁		b₂		…	b_n
A₁	a₁	c₁₁		c₁₂		…	c_1n
			x₁₁		x₁₂			x_1n
A₂	a₂	c₂₁		c₂₂		…	c_2n
			x₂₁		x₂₂			x_2n
…	…	…		…		…	…
A_m	a_m	c_m1		c_m2		…	cmn
			x_m1		x_m2			x_mn

Ввод исходных данных

Исходными данными для решения транспортной задачи являются:

	- матрица транспортных расходов;
	- предложение поставщиков;
	- спрос потребителей;

Напомним, что для ввода данного в ячейку рабочего листа EXCEL необходимо:

1. Селектировать ячейку;

2. Набрать вводимое данное на клавиатуре;

3. Нажать клавишу Enter.

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

Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи показан на рис 1.

	A	B	C	D	E	F	G	H	I
1
2
3			Матрица транспортных расходов						Предложение
4									поставщиков
5
6			6	7	3	5			100
7			1	2	5	6			150
8			8	10	20	1			50
9
10	Спрос потребителей		75	80	60	85
11
12
13
14
15
16
17

рис 1.

2. Разметка блоков ячеек рабочего листа EXCEL

Кроме исходных данных на рабочем листе EXCEL для решения транспортной задачи необходимо предусмотреть:

1.Блок ячеек "Матрица перевозок", в котором будут моделироваться объемы перевозок;

2.Блок ячеек "Фактически реализовано", в котором будет моделироваться фактическая реализация продукции;

3.Блок ячеек "Фактически получено", в котором будет моделироваться фактическое удовлетворение спроса;

4.Блок ячеек "Транспортные расходы по потребителям", в котором будут подсчитываться транспортные расходы по каждому потребителю;

5.Ячейку "Итого расходы", в которой будут моделироваться итоговые транспортные расходы по всем потребителям (целевая ячейка).

Для наглядности указанные блоки ячеек целесообразно обвести рамками. Рабочий лист EXCEL с размеченными блоками ячеек показан на рис.2.

Теперь в этих блоках ячеек можно формировать элементы математической модели и целевую функцию.

	A	B	C	D	E	F	G	H	I
1
2
3			Матрица транспортных расходов						Предложение
4									поставщиков
5
6			6	7	3	5			100
7			1	2	5	6			150
8			8	10	20	1			50
9
10	Спрос потребителей		75	80	60	85
11
12				Матрица перевозок
13			Потреб.1	Потреб.2	Потреб.3	Потреб.4
14		поставщик 1
15		поставщик 2
16		поставщик 3
17
18	Фактически получено
19
20	Транспортные расходы								расходы
21	по потребителям							Итого
22
23

Рис. 2.

Формирование элементов математической модели

Элементами математической модели транспортной задачи являются следующие суммы:

_ij - фактически реализовано i-ым поставщиком ;

, - фактически получено j-ым потребителями ;

Для нашей задачи m=3, n=4.

Рассмотрим процесс формирования этих сумм на рабочем листе EXCEL.

Вначале сформируем , в блоке "Фактически реализовано".

1.Заполните ячейки блока "Матрица перевозок" (С14:F16) числом 0,01.

2.Селектируйте первую ячейку блока "Фактически реализовано" (ячейка I14);

3.Наведите курсор на кнопку - автосуммирование и щелкните левой клавишей мыши;

4.Нажмите клавишу Delete;

5.Селектируйте первую строку блока "Матрица перевозок" (строка С14:F14);

6.Нажмите клавишу Enter;

7.Скопируйте формулу = СУММ (С14:F14) из первой ячейки блока "Фактически реализовано" на все остальные ячейки этого блока.

Сформируем теперь , - в блоке "Фактически получено".

Для этого выполните следующие действия:

1.Селектируйте первую ячейку блока "Фактически получено" (ячейка С18);

2.Наведите курсор на кнопку - автосуммирование и щелкните левой клавишей мыши;

3.Нажмите клавишу Delete;

4.Селектируйте первый столбец блока "Матрица перевозок" (Столбец С14:C16);

5.Нажмите клавишу Enter;

6.Скопируйте формулу = CУММ (С14:С16) из первой ячейки блока "Фактически получено" на остальные ячейки этого блока.

Формирование целевой функции

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

_ijC_ij в ячейки блока “Транспортные расходы по потребителям”

Для ввода этих формул выполните следующие действия:

1.Селектируйте первую ячейку блока “Транспортные расходы по потребителям” (ячейка С21);

2.Наведите курсор на кнопку - автосуммирование и щелкните левой клавишей мыши;

3.Нажмите клавишу “Delete ”;

4.Селектируйте первый столбец блока “Матрица Транспортных расходов” (столбец С6:С8);

5.Нажмите клавишу *;

6.Селектируйте первый столбец блока “Матрица перевозок” (столбец С14:С16);

7.Активируйте строку формул, наведя на неё курсор и щелкнув затем левой клавишей мыши;

8.Нажмите одновременно три клавиши: “CTRL”+“SHIFT”+“ENTER”;

9.Скопируйте формулу {=СУММ (С6:С8*С14:С16)} в остальные ячейки блока “Транспортные расходы по потребителям”;

Сформируем теперь целевую функцию транспортной задачи, выражаемую формулой _ijX_ij, в ячейку “Итого расходы”. Для этого:

Селектируйте ячейку “Итого расходы” (ячейка I21);

1. Наведите курсор на кнопку - автосуммирование и щелкните левой клавишей мыши;

2. Нажмите клавишу “Delete”;

3. Селектируйте блок ячеек “Транспортные расходы по потребителям (С21:F21);

4. Нажмите клавишу “Enter”;

После формирования элементов математической модели и целевой функции транспортной задачи рабочий лист EXСEL примет вид, показанный на рис. 3. Теперь можно приступить к настройке программы “Поиск решения”.

	A	B	C	D	E	F	G	H	I
1
2
3			Матрица транспортных расходов						Предложение
4									поставщиков
5
6			6	7	3	5			100
7			1	2	5	6			150
8			8	10	20	1			50
9
10	Спрос потребителей		75	80	60	85
11
12				Матрица перевозок
13			Потреб.1	Потреб.2	Потреб.3	Потреб.4
14		поставщик 1	0,01	0,01	0,01	0,01			0,04
15		поставщик 2	0,01	0,01	0,01	0,01			0,04
16		поставщик 3	0,01	0,01	0,01	0,01			0,04
17
18	Фактически получено		0,03	0,03	0,03	0,03
19
20	Транспортные расходы								расходы
21	по потребителям		0,15	0,19	0,28	0,12		Итого	0,74
22
23

Рис. 3.

Дата добавления: 2019-02-26; просмотров: 284; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 Следующая ⇒

Мы поможем в написании ваших работ!