Приближённый метод решения задач линейного программирования – метод индексов

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

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МОРСКОГО И РЕЧНОГО ФЛОТА

 ИМЕНИ АДМИРАЛА С.О. МАКАРОВА»

Кафедра математического моделирования и прикладной информатики

Моделирование транспортных процессов

Задание 9

 «Приближённый метод решения задач линейного программирования – метод индексов»

Выполнил: ст. группы УВТ-31

Ягодова В.В.

                                                                   Проверил: к.т.н., доцент
Костикова Е.В.

Санкт-Петербург

2019

Имеется m типов грузовых судов, которые обеспечивают перевозку грузов на n линиях. Заданы количество судов каждого типа (Ф1,…,Фi,…,Фm), плановый объем перевозок на линиях в тыс. т за навигацию (G1,…,Gj,…,Gn) с возможными его колебаниями (%), и провозная способность судна i-го типа на j-ой линии в тыс. т за навигацию (Пij), себестоимость перевозки в руб./т (Сij).

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

Последовательность решения задачи.

1. Составить математическую модель задачи;
2. Составить первоначальный план расстановки флота по линиям индексным методом;
3. Найти оптимальный план для модифицированной распределительной задачи;
4. Решить задачу расстановки флота на компьютере симплекс-методом;
5. Решить задачу в параметрической постановке, рассчитывая величину дополнительного объема Вj как процент от основного объема Gj;
6. Сравнить значения целевой функции, полученные по разным методам;
7. Написать выводы.

Исходные данные

Имеется m = 5 типов судов и n = 5 линий движения. В таблице 1 представлено количество судов каждого типа (Фi), плановый объем перевозок (Gj) и дополнительный объем перевозок на линиях (Вj).

Таблица 1

Провозная способность i-го типа судна на j-ой линии в тыс. т за навигацию:

[pic 1]

Себестоимость перевозок:

[pic 2]

1. Математическая постановка задачи

Искомые переменные:

Фij  - количество флота i-го типа, работающего на j-ой линии движения.

Целевая функция: [pic 3]

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

1. [pic 4]
2. [pic 5] для [pic 6] 

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

3) [pic 7] для [pic 8]

(т.е. количество судов каждого типа, расставленных по линиям движения, не может быть больше, чем имеется судов в наличии).

Распишем целевую функцию и ограничения для конкретной задачи:

[pic 9]

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

1. 62 Ф11 + 30 Ф21 + 44 Ф31 + 100 Ф41 + 72 Ф51 = 220 тыс. т;
2. 57 Ф12 + 28 Ф22 + 40 Ф32 + 90 Ф42 + 68 Ф52 = 170 тыс. т;
3. 48 Ф13 + 24 Ф23 + 35 Ф33 + 93 Ф43 + 65 Ф53 = 150 тыс. т;
4. 53 Ф14 + 23 Ф24 + 32 Ф34 + 85 Ф44 + 62 Ф54 = 200 тыс. т;
5. 65 Ф15 + 29 Ф25 + 46 Ф35 + 96 Ф45 + 70 Ф55 = 140 тыс. т;
6. Ф11 + Ф12 + Ф13 + Ф14 + Ф15 ≤ 4;
7. Ф21 + Ф22 + Ф23 + Ф24 + Ф25 ≤ 3;
8. Ф31 + Ф32 + Ф33 + Ф34 + Ф35 ≤ 5;
9.   Ф41 + Ф42 + Ф43 + Ф44 + Ф45 ≤ 6;
10. Ф51 + Ф52 + Ф53 + Ф54 + Ф55 ≤ 4.

1. Составление первоначального плана расстановки флота по линиям индексным методом

1. В матрице разместим строки (типы судов) в порядке ухудшения показателей (увеличения себестоимости перевозки).

Верхний левый угол – провозная способность Пij;

Нижний левый угол – себестоимость перевозки Сij;

Нижний правый угол – индекс Uij.

...