Задания для самостоятельной работы

Федеральное государственное образовательное бюджетное учреждение

Высшего образования

«ФИНАН

«ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ

РОССИЙСКОЙ ФЕДЕРАЦИИ»

Департамент анализа данных, принятия решений и финансовых технологий

И.Х.Утакаева

Решение задач линейного программирования (Транспортная задача)

Учебное пособие для проведения

семинара по компьютерному практикуму

Для бакалавров направления 38.03.01 «Экономика»

Электронное издание

Москва 2018

Постановка транспортной задачи

На m станциях отправления A₁, A₂, … , A_m сосредоточено соответственно a₁, a₂, … a_m единиц однородного груза. Груз следует перевезти в n пунктов назначения B₁, B₂, … , B_n, причём в каждый из пунктов нужно завести соответственно b₁, b₂, … , b_n единиц груза. Стоимость перевозки единицы груза из пункта A_i( )в пункт B_j( )задана и равна c_ij( , ). Считается, что общий запас груза на всех станциях отправления равен суммарной потребности груза на всех станциях назначения:

(1)

Требуется составить такой план перевозок, при котором общая стоимость всех перевозок окажется минимальной.

Все данные сведём в табл. 1 (матрица данных).

Таблица 1

Пункты назнач. Пункты отправ.	B₁	B₂	…	B_j	…	B_n	Запасы
A₁	c₁₁	c₁₂	…	c_1j	…	c_1n	a₁
…	…	…	…	…	…	…	…
A_i	c_i₁	c_i₂	…	c_ij	…	c_in	a_i
…	…	…	…	…	…	…	…
A_m	c_m₁	c_m₂	…	c_mj	…	c_mn	a_m
Потребности	b₁	b₂	…	b_j	…	b_n

Обозначим через x_ij количество единиц груза, предназначенного к отправке из пункта A_i в пункт B_j. Тогда количество груза, которое планируется к доставке в пункт B_j из всех пунктов отправления, составляет

Так как потребность в грузе пункта назначения B_j составляет b_j единиц, то должно быть выполнено равенство

В развёрнутом виде последние равенства представляют собой систему n линейных уравнений с m неизвестными:

(2)

С другой стороны, общее количество груза, отправленного из пункта A_i во все пункты B_j, составляет сумму

Таким образом, аналогично системе уравнений (2) получаем систему из m линейных уравнений с n неизвестными:

(3)

Полученные системы уравнений (2) м (3) объединим и запишем в виде системы из n + m линейных уравнений с n×m неизвестными:

(4)

Если величины x_ij свести в таблицу (табл. 2), то получим матрицу перевозок, по которой соотношения (4) легко проверяются: сумма элементов x_ij, расположенных в i–й строке равна запасу a_i на пункте A_i; сумма элементов x_ij из столбца j равна потребности b_j пункта B_j.

Таблица 2

Пункты назнач. Пункты отправ.	B₁	B₂	…	B_j	…	B_n	Запасы
A₁	c₁₁ x₁₁	c₁₂ x₁₂	…	c_1j x_1j	…	c_1n x_1n	a₁
…	c₂₁ x₂₁	c₂₂ x₂₂	…	c_2j x_2j	…	c_2n x_2n	a₂
A_i	…	…	…	…	…	…	…
…	c_i₁ x_i_1`	c_i₂ x_i₂	…	c_ij x_ij	…	c_in x_in	a_i
A_m	…	…	…	…	…	…	…
Потребности	c_m₁ x_m₁	c_m₂ x_m₂	…	c_mj x_mj	…	c_mn x_mn	a_m

Из условий задачи следует, что стоимость F всех перевозок равна сумме

(5)

Поскольку стоимость F должна быть минимальна, то естественным образом приходим к следующей задаче линейного программирования:

«Среди всех неотрицательных решений системы уравнений (4) найти такое, при котором форма F достигает наименьшего значения».

Сформулированная задача и является транспортной задачей по определению критерия стоимости перевозок.

Задание 1.С 3-х баз требуется доставить в магазины однородный товар. Пусть на базе А₁ имеется 50 единиц груза, на базе А₂ – 40 единиц, на базе А₃– 20 единиц. Указанный товар нужно отгрузить 4-м потребителям: В₁, В₂, В₃, В₄, потребности которых составляют соответственно 35, 25, 30, 25 единиц товара. Стоимость перевозки от базы до потребителей представлена в таблице:

Таблица 3

	В₁	В₂	В₃	В₄
А₁	³	²	⁴	⁶
А₂	²	³	¹	²
А₃	³	²	⁷	⁴

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

Необходимо создать экранную форму для ввода условия задачи.

Рисунок 1

В представленной форме каждой переменной и каждому коэффициенту задачи ставится в соответствие ячейкаMicrosoftExcel:

ü переменным задачи соответствуют ячейки E17:H19;

ü коэффициентам ЦФ соответствуют ячейки E26:H28;

ü левым частям системы ограничений задачи соответствуют ячейки I17:I19 и E20:H20;

ü правым частям системы ограничений соответствуют ячейки K17:K19 и E22:H22.

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

Рисунок 2

Левые части системы ограничений транспортной задачи

представляют собой суммы ячеек по каждой строке и каждому столбцу, отведенных для значений переменных задачи (E17:H19):

ü I17 – ограничение 1;

ü I18 – ограничение 2;

ü I19 – ограничение 3;

ü E20– ограничение 4;

ü F20– ограничение 5;

ü G20– ограничение 6;

ü H20– ограничение 7.

Используя обозначения соответствующих ячеек в Excel, формулу для системы ограничений можно записать как сумму ячеек каждой строки и каждого столбца, отведенных для переменных задачи (E17:H19) следующим образом:

ü поместить курсор в ячейку I17;

ü нажать кнопку «f_х» и вызвать окно «Вставка функции»;

ü выбрать в поле «Категория» категорию «Математические»;

ü в поле «Выберите функцию» выбрать функцию «СУММ» и нажать кнопку «ОК»;

ü в появившемся окне «Аргументы функции», в строку «Число1» ввести выражение E$17:H$17.

Рисунок 3

После ввода ячеек в строки «Число1» в окне «СУММ» появятся числовые значения (см. рис.3), а в экранной форме в ячейке I17 появится текущее значение, вычисленное по введенной формуле, то есть 0. Для ячеек I18 - ограничение 2 и I19 - ограничение 3 введенную формулу в I17 можно протянуть по строкам.

Для сумм по столбцам повторить следует повторить аналогичные действия:

ü поместить курсор в ячейку E20;

ü нажать кнопку «f_х» и вызвать окно «Вставка функции»;

ü выбрать в поле «Категория» категорию «Математические»;

ü в поле «Выберите функцию» выбрать функцию «СУММ» и нажать кнопку «ОК»;

ü в появившемся окне «Аргументы функции», в строку «Число1» ввести выражение E$17:Е$19.

Рисунок 4

После ввода ячеек в строки «Число1» в окне «СУММ» появятся числовые значения (см. рис.4), а в экранной форме в ячейке I20 появится текущее значение, вычисленное по введенной формуле, то есть 0. Для ячеек F20– ограничение 5, G20– ограничение 6, H20– ограничение 7 введенную формулу в Е20 можно также протянуть по столбцам.

В ячейку D34, в которой будет отображаться значение ЦФ, необходимо ввести формулу

по которой это значение будет рассчитано.

Формулу для расчета ЦФ можно записать как сумму произведений каждой из ячеек, отведенных для переменных задачи (E17:H19), на соответствующие ячейки, отведенные для тарифов - коэффициентов ЦФ (E26:H28) следующим образом:

ü поместить курсор в ячейку D34;

ü нажать кнопку «f_х» и вызвать окно «Вставка функции»;

ü выбрать в поле «Категория» категорию «Математические»;

ü в поле «Выберите функцию» выбрать функцию «СУММПРОИЗВ» и нажать кнопку «ОК»;

ü в появившемся окне «СУММПРОИЗВ», в строку «Массив 1» ввести выражение E$17:H$19, а в строку «Массив 2» – выражение E26:H28.

После ввода ячеек в строки «Массив 1» и «Массив 2» в окне «СУММПРОИЗВ» появятся числовые значения введенных массивов (см. рис.5), а в экранной форме в ячейке D34 появится текущее значение, вычисленное по введенной формуле, то есть 0.

Рисунок 5

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

Таблица 3

Объект математической модели	Выражение в Excel
Переменные задачи	E17:H19
Формула в целевой ячейке E13	=СУММПРОИЗВ(E17:H19; E26:H28)
Ограничения по строкамв ячейках I17 I18 I19	=СУММ(E17:H17) =СУММ(E18:H18) =СУММ(E19:H19)

Для реализации дальнейших этапов решения транспортной задачи необходимо вызвать «Поиск решения» и совершить следующие действия:

ü поставить курсор в поле «Оптимизировать целевую функцию»;

ü ввести адрес целевой ячейки $D$34 или сделать одно нажатие левой клавиши мыши на целевую ячейку в экранной форме – это будет равносильно вводу адреса с клавиатуры;

ü введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке «Минимум».

В окно «Поиск решения» в поле «Изменяя ячейки переменных» впишите адреса $E$17:$H$19. Необходимые адреса соответствующих ячеек можно вносить в поле «Изменяя ячейки» и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.

Рисунок 6

В поле «В соответствие с ограничениями» выбираем кнопку «Добавить»,после чего появится окно «Добавление ограничения».

Рисунок 7

В поле «Ссылка на ячейку» введите адрес ячейки системы ограничений $I$17. Это можно сделать как с клавиатуры, так и путем выделения мышью всех ячеек переменных непосредственно в экранной форме.В поле знака откройте список предлагаемых знаков и выберите знак «=». В поле «Ограничение» ввести адрес ячейки $K$17.

Рисунок 8

Аналогично следует ввестивсе оставшиеся ограничения по строкам: $I$18=$K$18

$I$19=$K$19

по столбцам:

$E$20=$E$22

$F$20=$F$22

$G$20=$G$22

$H$20=$H$22

после чего подтвердите ввод всех перечисленных выше условий нажатием кнопки «OK».

Окно «Поиск решения» после ввода всех параметров задачи представлено ниже. Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, используя кнопки «Изменить» или «Удалить».

В условии задачи имеются ограничения необходимо в «Параметрах поиска решений» установить флажок «Сделать переменные без ограничения неотрицательными».

После ввода всего условия задачи следует запустить «Поиск решения» на решение нажатием кнопки «Найти решение». В появившемся окне «Результаты поиска решения» следует выбрать «Сохранить найденное решение» и нажать «ОК».

Рисунок 9

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

Рисунок 10

Задания для самостоятельной работы

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

Таблица 4

Карьер	Строительный объект
Карьер	1	2	3	4
1	8	4	1	7
2	3	а	7	3
3	31-а	5	11	8

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

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

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

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

Таблица 5

Рабочие	Станки
Рабочие	С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

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

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

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

+2,5x₃₁+2x₃₂+ 2,2x₃₃+ 3x₃₄+ 2x₄₁+ 2,4x₄₂+ (2,4–а/20)x₄₃+ 2,8x₄₄→ 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 – целые.

Дата добавления: 2018-05-12; просмотров: 762; Мы поможем в написании вашей работы!

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

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