- •Геометрическая интерпретация линейного программирования
- •1.1 Общая математическая формулировка транспортной задачи
- •1.2 Методы решения транспортной задачи
- •1.2.1 Опорное решение транспортной задачи
- •1.2.2 Метод потенциалов
- •Глава 2. Постановка и решение транспортной задачи
- •2.1 Вербальная постановка транспортной задачи
- •2.2 Решение поставленной задачи распределительным методом «вручную»
- •2.4 Интерпретация результатов расчетов и выработка управленческого решения
- •2.3 Решение данной задачи с помощью средств excel
- •1.2 Общий вид решения и обобщение транспортной задачи
- •2. Содержательная постановка задачи
- •3. Математическая постановка задачи
- •4. Решение задачи
- •4.1 Математическое решение задачи
- •4.2 Решение задачи с помощью microsoft excel
- •5. Анализ результатов
- •4. Методика решения задач лп графическим методом
- •1. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
- •Тема 3. «Методы оценки привлекательности инвестиций».
2. Содержательная постановка задачи
Частным случаем задачи линейного программирования является транспортная задача. Проблема транспортировки включает поиск низко затратных схем распределения товарных запасов от многих источников до многих мест назначения.
Отгрузочными пунктами (поставщиками) являются фабрики, склады, отделы, из которых отправляются товары. Местом назначения также могут быть фабрики, склады, отделы, которые получают товары.
Информация необходимая для использования модели включает следущее:
- список отправных пунктов и пропускная способность каждого (количество поставок за определенный период);
- список мест назначения и их показатели спроса;
- стоимость транспортировки единицы продукции от каждого отправленного пункта до каждого места назначения. Эта информация сводится в транспортную таблицу.
3. Математическая постановка задачи
Пусть Xij - количество груза перевозимого из пункта i в пункт j.
А1=40; А2=50; В1=20; В2=30; В3=40;
3 5 7
С = 4 6 10
Таблица 5 - Начальные параметры
|
|
|
|
|
|
|
|
|
|
B1 |
B2 |
B3 |
|
|
|
|
|
A1 |
|
3 |
|
5 |
|
7 |
|
|
|
|
|
|
40 |
|
|
|
|
A2 |
|
4 |
|
6 |
|
10 |
50 |
|
|
|
|
|
|
|
|
|
|
|
20 |
30 |
40 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Целевая функция имеет вид:
Ограничение по запасам:
Х11 + Х12 + Х13 <= 40
Х21 + Х22 + Х23 <= 50
Xij>=0
Ограничение по спросу:
Х11 + Х21 <= 20
Х12 + Х22 <= 30
Х13 + Х23 <= 40
Этапы решения транспортной задачи:
Получение начального решения
Проверка решений на оптимальность
Усовершенствование несовершенных решений
Интуитивный подход.
Проверка на оптимальность и пересмотр несовершенных решений предусматривает анализ каждой пустой ячейки. Это выполняется так: одна единица перемещается в пустую ячейку и рассматривается влияние этого перемещения на стоимость. Если стоимость увеличилась, то это значит, что использование ячейки увеличило бы общие затраты. Если стоимость осталась не изменой, это значит альтернативный план с той же общей стоимостью. Если анализ показывает уменьшение - это значит возможно лучшее решение.
Таблица 6 - Заполнение ячеек
|
|
|
|
|
|
|
|
|
|
B1 |
B2 |
B3 |
|
|
|
|
|
A1 |
|
3 |
|
5 |
|
7 |
|
|
|
20 |
20 |
|
40 |
|
|
|
|
A2 |
|
4 |
|
6 |
|
10 |
50 |
|
|
|
10 |
40 |
|
|
|
|
|
|
20 |
30 |
40 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Целевая функция:
Z=3*20+5*20+6*10+10*40=60+100+60+400=620