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




Скачать 92.24 Kb.
Название5. Специальные задачи линейного программирования
Дата публикации24.09.2013
Размер92.24 Kb.
ТипРешение
skachate.ru > Спорт > Решение
Тема 5. Специальные задачи линейного программирования.

Транспортная задача и ее модификации. Методы решения ТЗ. Транспортная логистика. ЗЦЛП и методы ее решения. Задача коммивояжера. Задача о назначениях.
Решение транспортной задачи

Постановка задачи

Фирма должна отправить некоторое количество станков с трех складов в пять магазинов. На складах имеется соответственно 15, 25, 20 станков, а для пяти магазинов требуется соответственно 20, 12, 5, 8, 15 станков. Стоимость перевозки одного станка со склада в магазин приведена в таблице.



Wi - склад; Sj – магазин.

Как следует спланировать перевозку станков для минимизации стоимости перевозок?

Пусть Хij -количество станков, перевозимых со склада i в ма­газин j. Очевидно, что Xjj 0 , и в силу ограничений на возмож­ности поставки станков со складов (предложение) и спрос в мага­зинах они удовлетворяют следующим условиям:




Стоимость, равная

,

должна быть минимизированна при записанных выше ограничениях.

Записанная задача является задачей линейного программирования, но специального вида. Например, суммарный спрос станков равен сумме поставок. Сумма по первым ai трех ограничений дает тот же результат, что и сумма по bj по последним пяти ограничениям. Эти результаты обобщаются в транспортную задачу с m пунк­тами поставок ai (i=1,2,...,m) и n пунктами потребления bj (j=1,2,...,n). Причем

.
Если Cjj - стоимость транспортировки одного изделия из пункта производства i в пункт потребления j, то задача заключается в нахождении Xjj 0, удовлетворяющих соотношениям



и минимизирующих функцию .



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

Определение. Если в транспортной задаче (суммарные запасы не разны суммарным потребностям), то задачу называют открытой, в противном случае - закрытой.

Теорема ,1. Любая закрытая транспортная задача имеет решение и обладает оптимальным планом.

Теорема 2. Если ai и bj. не отрицательные числа, то любой спорный план составляется из целых перевозок.

Введем понятие матрицы планирования. Матрица планирования имеет вид:

Определение. План транспортной задачи является невырожденным, если он содержит m+n -1 положительных компонент.
Методы решения транспортной задачи

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

Схема решения транспортной задачи включает следующие этапы:

  1. Построение первоначального опорного плана.

  2. Корректировка опорного плана.

  3. Тест на оптимальность.


Построение первоначального опорного слана
Метод северо-западного угла

Пусть условие транспортной задачи задано в таблице.

Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребности первого потребителя В1 за счет запасов поставщика А1 . Для этого сравниваем a1 =100, b1=200, a1 < b1 , меньший из объемов записываем в левый нижний угол клетки А1В1 Запасы а1 полностью израсходованы, поэтому все остальные клетки первой строки прочеркиваем. Потребности В1 остались неудовлетворенными на 200-100=100 ед. Их берем у поставщика А2- Так как 100<250. то записываем в клетку А2B1 100 - потребности В1 полностью удовлетворены. Оставшиеся клетки в первом столбце прочеркиваем.

У поставщика А2 осталось 150 ед. груза. Удовлетворяем В2 за счет оставшегося у поставщика А2 груза. Для этого сравниваем этот остаток с потребностями В2 : 150<200. Записываем 150 единиц в клетку А2В2 и, так как запасы А2 полностью израсходованы, прочеркиваем оставшиеся клетки второй строки. Потребности В2 остались неудовлетворенными на 50 единиц. Удовлетворяем их за счет поставщика А3. В запаса А3 остается 150 единиц. Из них 100 единиц идет на потребности В3 и оставшиеся 50 единиц - на потребности В4 . Потребности В4 остались неудовлетворенными на 50 единиц. Их удовлетворяют за счет поставок А4. После этого в запасе А4 остается 300-50=250 единиц, которые идут на удовлетворение потребностей В5. Пустые клетки прочеркиваем.

В таблице в правых верхних углах клеток стоят числа, определяющие стоимость перевозок, а в левых нижних углах - числа, определяющие план перевозок. Является ли данный план невырожденным?

m+n-1=4+5-1=8.

В таблице ровно 8 занятых клеток, поэтому план является невырожденным опорным планом. Стоимость перевозок равна

С=100.10 + 100.2 + 150.7 + 50.5+100.3+50.2+50.16+250.13=6950 единиц стоимости.

Метод минимальной стоимости

Из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Рассмотрим предыдущую задачу.


План состоит из семи положительных перевозок, следовательно, является вырожденным опорным планом. Его стоимость ^ С=4300 единиц, то есть он ближе к оптимальному по сравнению с планом, полученным методом северо-западного угла.
Метод двойного предпочтения

В каждом столбце отличают знаком «V» клетку с наименьшей стоимостью. Затем то же самое проделывают для строк. В результате некоторые клетки имеют отметку «VV». В эти клетки помечают максимальные объемы перевозок, каждый раз исключая из рассмотрения соответствующие строки или столбцы. Затем распределяют перевозки по клеткам, отмеченным знаком «V». В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.


Стоимость С=4250 единиц. Число заполненных клеток равно 7 - опорный план вырожден.
Метод потенциалов

Используется для построения оптимального плана транспортной задачи.

Теорема. Если план X=(Хij) транспортной задачи является оптимальным, то ему соответствует система из m+n чисел Ui и Vj , удовлетворяющих условиям:


где числа Ui и Vj называются потенциалами соответственно поставщиков и потребителей.

Решение транспортной задачи сводится к следующей последовательности действий.

^ 1.Построение системы потенциалов. Используется условие для
занятых клеток (Хij >0)

Ui + Vj = Cij (1)

где Cij - стоимость перевозки единицы груза от i поставщика к j потребителю.

Систему потенциалов можно построить только для невырожденного опорного плана. Такой план содержит m+n-1 занятых -леток, по -этому для него можно составить систему из m+n-1 линейно независимых уравнений типа (1) с m+n неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому для определенности одному неизвестному придают нулевое значение. После этого остальные потенциалы определяются однозначно.

^ 2.Проверка выполнения условия оптимальности (для незанятых клеток). Вычислить величины Ui + Vj - Cij = tij. Если Для какой-либо клетки tij.>0, то условие оптимальности не выполняется. Значение tij записываются в правый низкий угол клетки.

^ 3.Выбор клетки, в которую необходимо послать перевозку. Осуществляется в духе симплекс-метода, в котором величине Zj соответствует сумма (Ui + Vj). Поэтому загрузке подлежит клетка, которой соответствует max(tij).

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

Транспортная задача, в которой называется закрытой, в противном случае - открытой. Для открытой задачи возможны два случая:

а) суммарные запасы превышают суммарные потребности ;

б) суммарные потребности превышает суммарные запасы .

Открытая транспортная задача решается приведением к закрытой задаче. Функция стоимости при этом не изменяется.

Случай (а): вводится фиктивный потребитель, потребности которого .

Случай (б): вводится Фиктивный поставщик, запасы которого .

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

Пример решения транспортной задачи

Матрица планирования имеет вид:



^ Построение первого опорного плана. Используем метод северо-западного угла. План должен иметь 4+3-1=6 положительных компонент. С=49.

Построение системы потенциалов. Осуществляем на основе занятых клеток.






План не оптимален, так как tij в клетках A3B1 и A3B2>0; max tij соответствует клетке A3B1 . То есть в нее следует послать перевозку, равную .
Определение

Построим вспомогательную таблицу


=1 из условия неотрицательности компонент плана. Вводится перевозка А3В1 , исключается перевозка А2В1. Полученный план помещаем в следующую расширенную матрицу планирования.




План не оптимален, так как tij в клетках А3 В2, А1В3 и A1B4>0. max tij соответствует клетке а3В2. То есть в нее следует послать перевозку, равную . Определение .

Построим вспомогательную таблицу



=2 из условия не отрицательности компонент плена. Вводится перевозка А3В2, исключается перевозка А2В2 . Полученный план помещаем в следующую расширенную матрицу планирования.


^ Расчет tij


План не оптимален, так как tij в клетках А1В3 и A1B4 >0. max tij соответствует клетке А1В3. To есть в нее следует послать перевозку, равную .

Определение .

Построим вспомогательную таблицу.



=1 из условия не отрицательности компонент плана. Вводится перевозка А1В3 , исключается перевозка А1В1. Полученный план помещаем в следующую расширенную матрицу планирования.



^ Расчет потенциалов




План оптимален, так как все tij .

Построим для данной задачи матрицы планирования методами минимальной стоимости и двойного предпочтения.
Метод минимальной стоимости



В данном случае метод потенциалов и методы минимальной стоимости и двойного предпочтения дают одинаковые результата для функции стоимости.
Контрольные задания

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

  1. . Проверить условие закрытости модели.

  2. . Построить плана перевозок методами северо-западного угла, минимальной стоимости и двойного предпочтения.

  3. . План, построенный методом северо-западного угла, привести к оптимальному с помощью метода потенциалов.


Вариант №4




Похожие:

5. Специальные задачи линейного программирования iconРеферат по дисциплине: «Управление в социальных и экономических системах»
Задачи линейного программирования. Постановка и геометрическая интерпретация задач линейного программирования. Методы линейного программирования....
5. Специальные задачи линейного программирования iconЗадача линейного программирования. Различные формы записи задачи...
Понятие о математическом моделировании экономических задач. Математические модели задач о рентабельности, о смесях, об оптимальном...
5. Специальные задачи линейного программирования iconКонтрольная работа №1 Предлагаются к самостоятельному изучению и...
Решение задачи линейного программирования на основе ее геометрической интерпретации (графический метод)
5. Специальные задачи линейного программирования iconРешение задачи линейного программирования Решить задачу линейного...
Решить задачу линейного программирования с помощью программы «Поиск решения» в ms excel
5. Специальные задачи линейного программирования iconЗадача   линейного программирования 10 Построение начального опорного плана перевозок
Одной из первых проблем, для которых были применены методы линейного программирования, явилась транспортная задача. Рассмотрим её...
5. Специальные задачи линейного программирования iconЗадачи 401 – 500
Ниже приведены комплексные задачи линейного программирования. Необходимо выполнить в указанном порядке следующие задания
5. Специальные задачи линейного программирования iconКонспекты (тезисы) лекций Лекция № Общая постановка задачи линейного...
Лекция № Общая постановка задачи линейного программирования. Элементы линейной алгебры и геометрии выпуклых множеств
5. Специальные задачи линейного программирования iconКонтрольная работа №2 по дисциплине «Методы оптимизации»
Приближенные методы решения задачи линейного программирования на примере транспортной задачи
5. Специальные задачи линейного программирования iconЗадачА №1
Используя графический метод, найти решение следующей задачи линейного программирования
5. Специальные задачи линейного программирования iconЛекция 2
Математическая модель задачи линейного программирования (злп) может быть записана в одной из трех форм

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница