Специальные задачи линейного программирования

 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ 

ФИНАНСОВЫЙ  УНИВЕРСИТЕТ 

ПРИ ПРАВИТЕЛЬСТВЕ  РОССИЙСКОЙ ФЕДЕРАЦИИ

(Финансовый  университет)

 

Челябинский филиал Финуниверситета

 

Факультет: Учетно-статистический

 

 

 

                                                                                                                                                                                                                                       

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

 

                                       по дисциплине  Исследование операций

 

ТЕМА  Специальные задачи линейного программирования

 

                                      

                                                          Вариант 3

 

 

 

Выполнил:	Чурбанова М.А.
Номер группы:	321
Номер личного дела:	11УЛД11703

 

 

Челябинск 2014

Задача 2.3.  Распределение самолётов по маршрутам

Постановка экономической  задачи:

 

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

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

 

Тип  самолёта	Число самолётов	Месячный объём перевозок  одним самолётом по авиалиниям
		1	2	3	4
1	40	15	10	20	50
2	25	30	20	10	17
3	30	25	50	30	45

 

Тип самолёта	Эксплуатационные расходы  на один рейс по данному маршруту, дол.
	1	2	3	4
1	10	20	25	40
2	70	22	15	45
3	40	50	40	65

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Необходимо найти такие  значения переменных Xij >= 0, которые минимизируют целевую функцию (суммарные расходы).

Пусть Xij – количество самолётов j – типа выделяемых по I – маршруту, Cij – расходы на один рейс самолёта j – типа по i– маршруту, Dij – месячный объём перевозок самолёта  ji – типа по I -  маршруту.

 

При заданных ограничениях:

 

а) по числу имеющихся  самолётов.

Х11 + Х12 + Х13 + Х14 = 40

Х21 + Х22 + Х23 + Х24 = 25

Х31 + Х32 + Х33 + Х34 = 30

 

б) по минимальному объёму перевозок

X11d11 + X21d21 + X31d31 >= 300

X12d21 + X22d22 + X32d32 >= 200

X13d13 + X23d23 + X33d33 >= 900

X14d14 + X24d24 + X34d34 >= 600

 

Решение:

1. Создание формы для решения задачи (рис.1) предполагает создание матрицы перевозок.

Для этого необходимо выполнить резервирование изменяемых ячеек  «В2:Е4» вводится «1».

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

 

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

 

 

 

 

 

 

 

 

 

2. Ввод граничных условий

Введение условий  маршрутов самолёта, т.е.

Ai = ∑ Xij,

Где Ai -  маршрут i-го самолёта;

       Xij – количество самолётов i – типа выделяемых по j – маршруту;

        n – количество типов

Для этого необходимо выполнить следующие операции:

• Курсор в ячейку «А2»
• Курсор на кнопку «Мастер функций», расположенную на панели инструментов. На экране появиться диалоговое окно Мастер функций шаг 1из2 (рис.2)

Рис.2. Мастер функций

 

• Курсор в окно «Категория» на категорию «Математические»
• курсор в окно Функции на СУММ
• На экране появляется диалоговое окно СУММ
• В строку «Число 1» ввести «В2:Е2» (рис.3)

 

Рис.3. Аргументы  функции

 

Аналогичные действия выполняются для ячеек «А3, А4» (рис.4)

• Курсор в ячейку «А3»
• Курсор на кнопку «Мастер функций», расположенную на панели инструментов. На экране появиться диалоговое окно Мастер функций шаг 1из2
• Курсор в окно «Категория» на категорию «Математические»
• курсор в окно Функции на СУММ
• На экране появляется диалоговое окно СУММ
• В строку «Число 1» ввести «В3:Е3»
• Курсор в ячейку «А4»
• Курсор на кнопку «Мастер функций», расположенную на панели инструментов. На экране появиться диалоговое окно Мастер функций шаг 1из2
• Курсор в окно «Категория» на категорию «Математические»
• курсор в окно Функции на СУММ
• На экране появляется диалоговое окно СУММ
• В строку «Число 1» ввести «В4:Е4»

 

Введение условия  типов самолёта, т.е. (рис.4)

Bj = ∑ Xij,

где Bj – тип j-го самолёта

       m -  количество маршрутов

Для этого необходимо выполнить следующие операции:

• Курсор в ячейку «В5»
• Курсор на кнопку «Мастер функций», расположенную на панели инструментов. На экране появиться диалоговое окно Мастер функций шаг 1из2
• Курсор в окно «Категория» на категорию «Математические»
• курсор в окно Функции на СУММ
• На экране появляется диалоговое окно СУММ
• В строку «Число 1» ввести «В2:В4»

Аналогичные действия выполняются  для ячеек «В5, С5, D5, Е5»

• Курсор в ячейку «С5»
• Курсор на кнопку «Мастер функций», расположенную на панели инструментов. На экране появиться диалоговое окно Мастер функций шаг 1из2
• Курсор в окно «Категория» на категорию «Математические»
• курсор в окно Функции на СУММ
• На экране появляется диалоговое окно СУММ
• В строку «Число 1» ввести «С2:С4»
• Курсор в ячейку «D5»
• Курсор на кнопку «Мастер функций», расположенную на панели инструментов. На экране появиться диалоговое окно Мастер функций шаг 1из2
• Курсор в окно «Категория» на категорию «Математические»
• курсор в окно Функции на СУММ
• На экране появляется диалоговое окно СУММ
• В строку «Число 1» ввести «D2:D4»
• Курсор в ячейку «Е5»
• Курсор на кнопку «Мастер функций», расположенную на панели инструментов. На экране появиться диалоговое окно Мастер функций шаг 1из2
• Курсор в окно «Категория» на категорию «Математические»
• курсор в окно Функции на СУММ
• На экране появляется диалоговое окно СУММ
• В строку «Число 1» ввести «Е2:Е4»

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

 

Рис.4. Ввод граничных  условий

 

 

 

 

 

 

 

 

 

 

3. Ввод исходных данных (рис.5)

В конкретном примере  осуществляется  распределение числа  самолётов трёх типов по авиалиниям (ячейки «А9:А11»), перевоза по каждой из четырёх авиалиний               (ячейки «В8:Е8»), эксплуатационные расходы на один рейс по данному маршруту. дол. ( блок «В9:Е11»). А также Месячный объём перевозок одним самолётом по авиалиниям      (блок «В17:Е19»)

Рис.5. Ввод исходных данных и граничных условий

 

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

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

Пусть Xij – количество самолётов j – типа выделяемых по I – маршруту, Cij – расходы на один рейс самолёта j – типа по i– маршруту, Dij – месячный объём перевозок самолёта  ji – типа по I -  маршруту.

 

F = ∑ ∑ Xij * Cij

Для этого:

• Поместим курсор в ячейку В12(рис.7)
• Курсор на кнопку «Мастер функций», расположенную на панели инструментов.

      На экране появляется диалоговое окно Мастер функций шаг 1 из 2

 

Рис.7. Мастер функций

• Курсор в окно «Категория» на категорию «Математические».
• Курсор в окно Функции на СУММПРОИЗВ
• На экране появляется диалоговое окно СУММПРОИЗВ (рис.8)
• В строку «Массив 1» ввести «В9:Е11»
• В строку «Массив 2» ввести «В2:Е4»

 

Рис.8. Аргументы  функции

 

 

 

 

 

• «ОК» подтверждение окончания ввода адресов массивов.

В поле ячейки «В12» появится некоторое числовое значение, равное произведению единичных  распределений самолётов на эксплуатационные расходы на один рейс по данному маршруту. дол. (число 442 в данной задаче). (рис.9).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Поиск решения (рис.10).

• В строке «Меню» указатель мыши поместить на имя «Сервис». В развёрнутом меню выбрать команду «Поиск решения». Появится диалоговое окно.

 

Рис.10. Меню «Поиск решения»

 

2. Назначить ячейку для целевой функции (рис.11)

(установить целевую  ячейку, указать адрес изменяемых  ячеек)

• Поместить курсор в строку «Установить целевую ячейку»
• Вводим адрес ячейки «$B$12»
• Вводим тип целевой функции. Целевая функция по условию задачи равна минимуму значению
• Поместить курсор в строку «Изменяя ячейки»
• Вводим искомых переменных «$B$2:$E$4»

 

Рис.11. Ввод адресов  исходных данных

 

3. Вводим ограничения (рис.12;13)

• Поместим указатель мыши на кнопку «Добавить». Появляется диалоговое окно «Добавление ограничения»
• В строке «Ссылка на ячейку» вводим адрес «$A$2:$A$4»
• Знак ограничения «=»
• В строке «Ограничение» вводим «$A$9:$A$11»

 

Рис.12. Добавление ограничения

 

• Курсор мышки наводим на кнопку «Добавить». На экране вновь появляется диалоговое окно «Добавление ограничения»
• Вводим остальные ограничения «$B$2:$E$4»
• Знак ограничения «цел»
• В строке «Ограничение» автоматически вводится «целое»
• Курсор мышки наводим на кнопку «Добавить». На экране вновь появляется диалоговое окно «Добавление ограничения»
• Вводим остальные ограничения «$B$8:$E$8»
• Знак ограничения «<=»
• В строке «Ограничение» автоматически вводится «$B$20:$E$20»
• После введения последнего ограничения кнопка «ОК». На экране появляется диалоговое окно «Поиск решения» с введёнными условиями.

 

Рис.13. Введены  все условия задачи

 

 

4. Вводим параметры для решения задачи (рис.14;15)

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

 

 

 

Рис.14. Ввод параметров

 

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

Рис.15.Результаты поиска решения и исходная таблица  с заполненными ячейками