4758

4. Назначение целевой функции.

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

к j -му заказчику; xij — объем поставки (число тонн песка) от i -го карьера к j -му заказчику.

Для этого нужно:

-установить курсор в ячейку С13. В данную ячейку будет помещаться значение целевой функции после решения задачи;

-на панели инструментов нажать кнопку Мастер функций. В диалоговом окне Мастер функций выбрать категорию Математические и функцию

СУММПРОИЗВ;

-в окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией.

Взадаче целевая функция представляет собой произведение удельных затрат на доставку груза (расположенных в блоке ячеек С10:G12) и объемов поставок для каждого участка (содержимое ячеек С2:G4). Для этого:

-в поле Массив 1 указать адреса С10:G12;

-в поле Массив 2 указать адреса С2:G4;

-подтвердить окончание ввода адресов массивов. В поле ячейки С13 появится некоторое числовое значение, равное произведению единичных поставок на удельные коэффициенты затрат по доставке грузов (число 53 в данной задаче, рис. 1).

5.Ввод зависимостей и ограничений из математической модели. Выполним команду меню Сервис \ Поиск решения. В диалоговом окне

Поиск решения нужно:

назначить целевую ячейку – в данном случае С13;

ввести направление целевой функции – Минимальному значению;

в строке Изменяя ячейки ввести диапазон С2:G4 (адреса искомых переменных);

ввести ограничения, для этого нажать на кнопку Добавить и

ввести данные в диалоговое окно Добавление ограничения ; В результате диалоговое окно Поиск решения выглядит следующим образом

(рис.2):

Рис. 2. Диалоговое окно Поиск решения

В диалоговом окне Поиск решения нужно нажать на кнопку Параметры и в диалоговом окне Параметры поиска решения установить флажки в окнах

Линейная модель и Неотрицательные значения .После этого нужно нажать на кнопку Выполнить.

6. Просмотр результатов и печать отчета.

После выполнения всех вышеуказанных действий на экран выводится окно

Результаты поиска решения.

-В окне Тип отчета нужно выбрать интересующий вид отчета и нажать ОК.

-Внизу страницы экрана содержится сообщение Отчет по результатам. Щелкнуть на этом сообщении, на экран выводятся результаты решения задачи, которые можно распечатать.

Вматрице перевозок содержатся оптимальные объемы поставок грузов от карьерам к участкам дорог, дающие минимум затрат на доставку. Значение целевой функции содержится в ячейке С13 и для конкретной задачи равно 2300 (рис. 3).

Из вышеизложенного можно сделать следующий вывод:

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

от первого карьера нужно отправить 150т, 250т и 100т песка на участки

В1, В2 и В4 соответственно;

от второго карьера нужно отправить 100т и 200т песка на участки В2 и В3 соответственно;

от третьего карьера нужно отправить 100т песка на участок В5.

Рис. 3. Значение целевой функции.

II ) а) Определим, как изменится план перевозок, если ввести запрет на перевозки от первого карьера до второго участка работ. Для этого присвоим значению D10 достаточно большое число, т.е. высокую стоимость перевозки, например, D10=1000. Выполним команду меню Сервис \ Поиск решения. Результат поиска решения представлен на рис. 4.

Рис. 4. Результат поиска решения (1 изменение).

Значение целевой функции на этом плане составило 3100 ед., т.е. на 800 ден. ед. больше, чем при оптимальном плане.

б) Определим, как изменится план перевозок, если объем перевозок от первого карьера до второго участка работ будет ограничен 3 тоннами. Выполним команду меню Сервис \ Поиск решения. В диалоговом окне Поиск решения добавим ограничение D2<=3. Результат поиска решения представлен на рис. 5.

Рис. 5. Результат поиска решения (2 изменение).

Значение целевой функции на этом плане составило 3088 ед., т.е. на 788 ден. ед. больше, чем при оптимальном плане.

Контрольные вопросы:

1.В чем состоит особенность ТЗ как частного случая 3ЛП? 2.Что называется перевозками и планом перевозок в ТЗ?

3.Чему соответствует число уравнений ТЗ и каково число независимых уравнений?

4.Что такое базисные и свободные переменные ЗЛП? Что такое несбалансированная или открытая ТЗ?

5.Как находилась целевая функция?

6.На основании чего делаются выводы в изменениях условий?

Задача 2 (дальнобойщик).

Требуется распределить автомобили трех типов по транспортным линиям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех линий соответственно не менее 300, 200, 900 и 600 т. груза.

Ниже в табл. 2,3 приведены исходные данные.

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

i 1 j 1

Ограничения:

4

x1 j 40; - Ограничения по числу автомобилей,

j 1

4

x2 j 25;

j 14

x3 j 30;

j 1

По смыслу задачи: xij - целые неотрицательные числа.

Полученную ЗЛП будем решать средствами Excel, используя надстройку

Сервис \ Поиск решения.

Выполним последовательно следующие действия в среде Excel:

1.Создадим форму для ввода условий задачи и введем в нее исходные данные (рис.6).

2.Укажем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Оптимальные значения компонент матрицы решений будут помещены в ячейках I12:L14, оптимальное значение целевой функции – в ячейке H16.

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

3.Введем зависимость для целевой функции, для этого нужно: установить курсор в ячейку H16, на панели инструментов нажать кнопку Мастер функций. В диалоговом окне Мастер функций

выбрать категорию Математические и функцию СУМПРОИЗВ;

Рис.7. Диалоговое окно функции СУМПРОИЗВ.

В диалоговом окне Аргументы функций в строку «Массив 1» ввести C5:F7, в строку «Массив 2» ввести I5:L7, в строку «Массив 3» ввести

I12:L14 (рис.7).

4. Введем зависимости для ограничений:

-в ячейки В10, В11, В12 нужно ввести функции СУММ(I12:L12), СУММ(I13:L13), СУММ(I14:L14) соответственно; в ячейки D 10, D 11, D 12 введем соответственно значения 30, 45, 40.

-в ячейки В13, В14, В15, В16 нужно ввести функции СУММПРОИЗВ(C5:C7;I12:I14), СУММПРОИЗВ(E5:E7;K12:K14), СУММПРОИЗВ(F5:F7;L12:L14), СУММПРОИЗВ(D5:D7;J12:J14)

соответственно; в ячейки D 13, D 14, D15, D16 введем соответственно значения 300, 200, 900, 600.

Врезультате получим следующую форму для решения задачи (рис.8):

Рис. 8. Форма для решения задачи.

5. Выполним команду меню Сервис \ Поиск решения. В диалоговом окне

Поиск решения нужно:

назначить целевую ячейку – в данном случае H16;

ввести направление целевой функции – Минимальному значению;

в строке Изменяя ячейки ввести диапазон I12:L14 (адреса искомых переменных);

ввести ограничения, для этого нажать на кнопку Добавить и ввести данные в диалоговое окно Добавление ограничения;

Врезультате диалоговое окно Поиск решения выглядит следующим образом (рис. 9-10):

Рис. 9. Диалоговое окно Поиск решения Рис. 10. Диалоговое окно Параметры поиска решения

6.Введем параметры для решения ЗЛП. Для этого в диалоговом окне Поиск решения нужно нажать на кнопку Параметры и в диалоговом окне

Параметры поиска решения установить флажки в окнах Линейная модель и Неотрицательные значения (рис.10). После этого нужно нажать на кнопку Выполнить.

Через некоторое время появляется диалог Результаты поиска решения и

Полученное решение означает, что на 1-ю транспортную линию нужно назначить 12 автомобилей 1-го типа; на 2-ю транспортную линию нужно назначить 5 автомобилей 3-го типа; на 3-ю транспортную линию – по 18 автомобилей 1-го и 2-го типов соответственно; на 4-ю линию – 23 автомобиля 2-го типа.

В этом случае будут задействованы все 30 автомобилей 1-го типа и 41 автомобиль 2-го и 5 автомобилей 3-го типов соответственно. По каждой из четырех транспортных линий будет перевезено соответственно 300, 200, 900 и 600 т. груза.

Минимальные суммарные эксплуатационные расходы составят 50835 долл.

Контрольные вопросы:

1.Чем отличается данная ТЗ от предыдущей?

2.Объясните расчет ограничений по числу автомобилей.

3.Как рассчитать объем перевозок конкретным типом автомобиля по конкретной линии?

4.Объясните почему полученная матрица решений оптимальна.

Задача 3 (о назначениях).

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

Решение: Экономико-математическая модель задачи.

Пусть на автопредприятии (или в подразделении автопредприятия) имеются n водителей S1 , S2 , …, Si , …, Sn (i 1,2,...,n) , которых необходимо

назначить (распределить) по n маршрутам R1 , R2 , …, R j , …, Rn ( j 1,2,...,n) . На каждом из указанных маршрутов может работать любой из

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

xij 1, а остальные элементы этой строки будут равны 0. Таким образом,