Ввод данных для решения закрытой транспортной задачи

ВВЕДЕНИЕ

Лабораторная работа “Транспортная задача” предназначена для закрепления теоретических знаний, полученных студентами направления 140100 “ Теплоэнергетика“ при изучении методов линейного математического программирования.

 

ЦЕЛЬ РАБОТЫ

 

Решить транспортную задачу при помощи табличного процессора (ТП) Microsoft Excel. Исследовать, как влияют на целевую функцию изменение тарифов перевозок и запасов угля.

 

ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНия

2.1. Общая формулировка транспортной задачи

Найти оптимальный план перевозок некоторого однородного груза из m пунктов отправления А₁, А₂,…, А_m в n пунктов назначения В₁, В₂,…, В_n. В качестве критерия оптимальности принять минимум суммарной стоимости перевозок всего груза.

Требуется так организовать перевозку угля, чтобы:

1) удовлетворить все заявки электростанций;

2) вывезти все запасы угля с месторождений;

3) суммарная стоимость всех перевозок топлива была бы наименьшей.

Введем следующие обозначения:

- тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения;

- запасы груза в i-м пункте отправления;

- потребности в грузе в j-том пункте назначения;

- планируемое количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения.

 

2.2. Математическая постановка транспортной задачи

Найти минимум

(1)

при условиях

; (2)

; (3)

. (4)

Всякое неотрицательное решение систем линейных уравнений (2) и (3), определяемое матрицей , называется планом транспортной задачи.

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

 

ПРИМЕР ТРАНСПОРТНОЙ ЗАДАЧИ

3.1. Постановка

Имеется 5 месторождений каменного угля с запасами топлива и 5 электростанций , годовой расход топлива которых составляет , соответственно. Стоимость перевозки единицы топлива от i-го месторождения к j-той станции (в таблице находится на пересечении соответствующих строк и столбцов) и значения запасов и расходов заданы в таблице 1.

Исходные данные

Таблица 1

	Электро-станции	В1	В2	В3	В4	В5	Всего
Месторожде-ния	Запасы / расходы	b1=330	b2=140	b3=440	b4=1110	b5=575
А1	а1=1000
А2	а2=295
А3	а3=200
А4	а4=500
А5	а5=600
всего

 

3.2. Математическая запись

План перевозок	Матрица тарифов
(5)	(6)
Целевая функция
(7)
Ограничения
	(8)

ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ

(закрытая транспортная задача)

4.1. Выполнить постановку задачи

4.2. Описать математическую модель транспортной задачи.

4.4. Решить закрытую транспортную задачу симплекс-методом при помощи табличного процессора (ТП) Microsoft Excel.

 

Ввод данных для решения закрытой транспортной задачи

1. Для закрытой транспортной задачи создаем форму для ввода условий в виде таблицы. Количество строк и столбцов этой формы должно соответствовать количеству запасов и расходов топлива. Вводим при помощи клавиатуры в ячейки В5 – В9 коэффициенты ; в ячейки С4 – G4 – коэффициенты ; в ячейки C5 – G9 – коэффициенты . Изменение исходных данных можно осуществлять только в этой форме (рис. 4.1).

Рис.4.1. Форма для ввода условий задачи

 

2. Вводим зависимости из созданной математической модели. Для этого на том же листе создается аналогичная форма, содержимое которой отличается от содержимого формы для ввода данных (рис.4.2).

Рис.4.2. Форма для ввода зависимостей из математической модели

 

Ячейки С16 – G20 являются адресом матрицы независимых переменных, при заполнении они должны быть равными нулю. Ячейки C15 – G15должны содержать действия, в результате которых выполняется ограничение (2). Ячейка С15 является суммой значений ячеек С16 – С20.Ее заполнение осуществляемпри помощи Мастера функций (см.приложение).

2.1. Курсором выделить заполняемую ячейку С15;

2.2. Запустить Мастер функцийи в диалоговом окне Мастер функций – шаг 1 из 2 курсором выбрать в окне Категория категорию Математические, ав окне Функции – СУММ;

2.3. Нажать кнопку ОК;

2.4. В диалоговом окне Аргументы функциив поле Число 1 ввести массив С16:С20. Справа от знака равенства появятся численные значения этого массива, а внизу окна – результат суммирования (рис.4.3);

2.5. Курсором нажать кнопкуOK.

Рис.4.3.

Аналогичные действия выполняются при заполнении ячеек D15, E15, F15 и G15, которые являются суммами соответствующих столбцов.

Ячейки В16 – В20 должны содержать действия, в результате которых выполняется условие (3). Рассмотрим принцип заполнения ячейки В16, остальные ячейки этого столбца заполняются аналогично.

2.6. Выделить курсором ячейку В16;

2.7. Выполнить операции по пп. 2.2 – 2.3;

2.8. В поле Число 1 ввести массив C16:G16;

2.9. Курсором нажать кнопкуOK .

Ячейка Н15 является суммой ячеек с С15 по G15, а ячейка В21 – суммой ячеек с В16 по В20. Их заполнение осуществляется по уже известному алгоритму.

 

3. Ввести зависимость для целевой функции, выполнив следующую последовательность операций:

3.1. Курсором выделить ячейку для целевой функции: например F10;

3.2. Запустить Мастер функций;

3.3. В диалоговом окне Мастер функций – шаг 1 из 2 выбрать в окне Категория категорию Математические, а в окне Функции – СУММПРОИЗВ;

3.4. Нажать кнопку ОК;

3.5. В появившемся диалоговом окне СУММПРОИЗВ в поле массив 1 ввести адреса матрицы коэффициентов целевой функции С5:G9, а в поле массив 2 ввести адреса матрицы независимых переменных C16:G20 (рис.4.4);

3.6. Курсором нажать кнопкуOK.

На этом ввод данных в таблицы (рис. 4.1, рис. 4.2) закончен.

Рис.4.4.