Материал: 4758

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. Таким образом,