Автор работы: Пользователь скрыл имя, 01 Февраля 2013 в 10:29, задача
3 Задачи.
Условие задачи - Нефтегазодобывающая компания имеет 5 морских буровых установок на шельфовых проектах. Для обеспечения своевременного снабжения буровых материалами и провиантом, компания взяла в аренду 5 судов, которые необходимо распределить по маршрутам следования А, В, С, Д, Е. Последние отличаются различной отдаленностью от Береговой Базы снабжения и погодными условиями. Суда имеют различные характеристики по грузовместимости, маневренности, скорости, дней автономности, количеству пассажиров и себестоимости перевозок. Тем не менее, любое судно по своим характеристикам может работать на любом из планируемых маршрутов.
1. Задача о назначениях
Условие задачи
Нефтегазодобывающая компания имеет 5 морских буровых установок на шельфовых проектах. Для обеспечения своевременного снабжения буровых материалами и провиантом, компания взяла в аренду 5 судов, которые необходимо распределить по маршрутам следования А, В, С, Д, Е. Последние отличаются различной отдаленностью от Береговой Базы снабжения и погодными условиями. Суда имеют различные характеристики по грузовместимости, маневренности, скорости, дней автономности, количеству пассажиров и себестоимости перевозок. Тем не менее, любое судно по своим характеристикам может работать на любом из планируемых маршрутов.
Необходимо определить каким
образом следует расставить
Решение
1. Исходная таблица 1.1. В каждой строке найдем наименьший элемент и запишем его в соответствующей строке табл. 1.2.
|
А |
В |
С |
Д |
Е | |
1 |
45 |
53 |
37 |
36 |
42 | |
2 |
32 |
48 |
51 |
55 |
31 | |
3 |
42 |
54 |
45 |
41 |
48 | |
4 |
36 |
46 |
51 |
44 |
50 | |
5 |
51 |
55 |
56 |
46 |
44 | |
36 |
31 |
41 |
36 |
44 |
2. Вычтем элементы табл. 1.2. из строк табл. 1.1. и получим табл. 1.3.
Таблица 1.3.
9 |
17 |
1 |
0 |
6 |
1 |
17 |
20 |
24 |
0 |
1 |
13 |
4 |
0 |
7 |
0 |
10 |
15 |
8 |
14 |
7 |
11 |
12 |
2 |
0 |
Таблица 1.4.
0 |
10 |
1 |
0 |
0 |
3. В Таблице 1.3. найдем минимальные числа по столбцам и запишем их в таблице 1.4. Вычтем из элементов таблицы 1.3. числа из таблицы 1.4.
Получим таблицу 1.5. Теперь в каждой строке и в каждом столбце таблицы 1.5. есть, по крайней мере, один нулевой элемент.
Таблица 1.5.
9 |
7 |
0 |
0 |
6 |
1 |
7 |
19 |
24 |
0 |
1 |
3 |
3 |
0 |
7 |
0 |
14 |
8 |
14 | |
7 |
1 |
12 |
2 |
0 |
4. Проведем минимальное число линий, проходящих через все нулевые клетки строк и столбцов таблица 1.5.
5. Найдем наименьший среди элементов, через которые не проходит ни одна из проведенных прямых (число 1).
6. Вычтем число 1 из всех элементов, через которые не проходят прямые.
7. Прибавим число 1 в клетки, где прямые пересекаются.
8. Остальные клетки, через которые проходит только одна прямая, оставим без изменений.
Получим таблицу 1.6.
Таблица 1.6.
А |
В |
С |
Д |
Е | |
1 |
8 |
6 |
0 |
0 |
6 |
2 |
0 |
6 |
19 |
24 |
0 |
3 |
0 |
2 |
3 |
0 |
7 |
4 |
0 |
0 |
15 |
9 |
15 |
5 |
6 |
0 |
12 |
2 |
0 |
9. Проанализируем данные, полученные в таблице 1.6.
Оптимальное решение задачи определяют клетки с нулевой себестоимостью. Выберем возможные решения по нулевым клеткам:
Таким образом:
Окончательное решение задачи: А2; В4; С1; Д3; Е5.
10. Проверка:
Находим сумму общей себестоимости по данным исходной таблицы 1.1. по оптимальному варианту. Она составляет 188.
Любые другие варианты дают сумму большую, чем в оптимальном варианте, например, равную 201 и более.
Эту же задачу решим для поиска максимума прибыли или доходов. Для этого:
1. В исходной таблице найдем максимальное число (С5 - 56).
2. Вычтем максимальное число из всех клеток табл.1.1.
Затем повторим все действия в той же последовательности. Получим оптимальную расстановку судов, которая даст максимум доходов и прибыли.
Решение
Таблица 1.1. Таблица 1.2.
|
А |
В |
С |
Д |
Е | |
1 |
11 |
3 |
19 |
20 |
14 | |
2 |
24 |
8 |
5 |
1 |
25 | |
3 |
14 |
2 |
11 |
7 |
8 | |
4 |
20 |
10 |
5 |
16 |
6 | |
5 |
5 |
1 |
0 |
10 |
12 | |
3 |
1 |
2 |
5 |
0 |
2. Вычтем элементы таблицы 1.2. из строк таблицы 1.1. и получим таблицу 1.3.
Таблица 1.3.
8 |
0 |
16 |
17 |
11 |
23 |
7 |
4 |
0 |
24 |
12 |
0 |
9 |
5 |
6 |
15 |
5 |
0 |
11 |
1 |
5 |
1 |
0 |
10 |
12 |
Таблица 1.4.
5 |
0 |
0 |
0 |
1 |
3. В таблице 1.3. найдем минимальные числа по столбцам и запишем их в таблице 1.4. Вычтем из элементов таблицы 1.3. числа из таблицы 1.4.
Получим таблицу 1.5. Теперь в каждой строке и в каждом столбце таблицы 1.5. есть, по крайней мере, один нулевой элемент.
3 |
0 |
16 |
17 |
10 |
18 |
7 |
4 |
0 |
21 |
7 |
0 |
9 |
5 |
5 |
5 |
0 |
11 |
0 | |
1 |
0 |
10 |
11 |
4. Проведем минимальное число линий, проходящих через все нулевые клетки строк и столбцов таблица 1.5.
5. Найдем наименьший среди
элементов, через которые не
проходит ни одна из
6. Вычтем число 3 из всех элементов, через которые не проходят прямые.
7. Прибавим число 3 в клетки, где прямые пересекаются.
8. Остальные клетки, через которые проходит только одна прямая, оставим без изменений.
Получим таблицу 1.6.
А |
В |
С |
Д |
Е | |
1 |
0 |
0 |
19 |
17 |
7 |
2 |
15 |
7 |
7 |
0 |
18 |
3 |
4 |
0 |
12 |
5 |
2 |
4 |
10 |
8 |
0 |
14 |
0 |
5 |
0 |
4 |
0 |
13 |
11 |
9. Проанализируем данные, полученные в таблице 1.6.
Выберем возможные решения по нулевым клеткам:
Таким образом:
Окончательное решение задачи: А1; В3; С5; Д2; Е4.
10. Проверка:
Находим сумму общей доходности по данным исходной таблице 1.1. по оптимальному варианту. Она составляет 260.
Любые другие варианты дают сумму меньшую, чем в оптимальном варианте.
2. Анализ многономенклатурных
товарных запасов с