Курсовая работа: Решение задач линейного программирования транспортной задачей

k=R+L-1

Значение оценки показывает на сколько сократятся(увеличатся) затраты на перевозку единиц продукции если в эту ячейку переместить значение.

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

Таблица 4

Изменение начальной таблицы

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

Метод MODI (модифицированное распределение).

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

Этот метод состоит из шагов:

1) Сделать начальное распределение (интуитивный подход), проверить матрицу на полноценность, в случае необходимости провести корректировку.

2) Получить номер индекса для каждой строки и столбца. Делая это используя только заполненные ячейки. Всегда есть по крайней мере одна заполненная ячейка в каждом столбце и строке.

а) начинаем, назначая ноль в первой строке

б) определить индекс столбца для любой заполненной ячейки в строке 1, используя следующие соотношения:

индекс столбца = U;

индекс строки = V;

затраты ячейки = С;

U = C-V

в) Каждое новое значение столбца позволит вычислить по крайней мере 1 новое значение строки и наоборот. Продолжайте эту процедуру пока все строки и столбцы будут заполнены индексами.

3) Получить оценки для пустых ячеек

W – оценка ячейки

W = C- (U+V)

1 – C: W = 7-(0+9) = -2

2 – A: W = 4-(1+3)= 0

4) Получение наилучшего решения

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

2. Содержательная постановка задачи

Частным случаем задачи линейного программирования является транспортная задача. Проблема транспортировки включает поиск низко затратных схем распределения товарных запасов от многих источников до многих мест назначения.

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

Информация необходимая для использования модели включает следущее:

- список отправных пунктов и пропускная способность каждого (количество поставок за определенный период);

- список мест назначения и их показатели спроса;

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

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

Пусть Xij - количество груза перевозимого из пункта i в пункт j.

А1=40; А2=50; В1=20; В2=30; В3=40;

3 5 7

С = 4 6 10

Таблица 5

Начальные параметры

Целевая функция имеет вид:

Ограничение по запасам:

Х11 + Х12 + Х13 <= 40

Х21 + Х22 + Х23 <= 50

Xij>=0

Ограничение по спросу:

Х11 + Х21 <= 20

Х12 + Х22 <= 30

Х13 + Х23 <= 40

Этапы решения транспортной задачи:

1)  Получение начального решения

2)  Проверка решений на оптимальность

3)  Усовершенствование несовершенных решений

Интуитивный подход.

Проверка на оптимальность и пересмотр несовершенных решений предусматривает анализ каждой пустой ячейки. Это выполняется так: одна единица перемещается в пустую ячейку и рассматривается влияние этого перемещения на стоимость. Если стоимость увеличилась, то это значит, что использование ячейки увеличило бы общие затраты. Если стоимость осталась не изменой, это значит альтернативный план с той же общей стоимостью. Если анализ показывает уменьшение – это значит возможно лучшее решение.

Таблица 6

Заполнение ячеек

Целевая функция:

Z=3*20+5*20+6*10+10*40=60+100+60+400=620

4. Решение задачи

4.1 Математическое решение задачи

Страницы: 1, 2, 3, 4, 5, 6