Экономико-математические методы. Линейное программирование

Требуется составить такой  план перевозок, при котором все  заявки пунктов потребления полностью  выполнялись бы пунктами отправления, а общая стоимость перевозок  была минимальной.

При такой постановке данную задачу называют транспортной задачей  по критерию стоимости.

В общем виде исходные данные представлены в таблице 9.

 

Таблица 9

 

Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения

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

П.1 Алгоритм метода минимального элемента.

1. Из распределительной таблицы 9 выбирают наименьшую стоимость и в клетку, которая ей соответствует, помещают меньшее из чисел a_i или b_j (если таких клеток несколько, то выбирают любую);
2. Из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и то и другое;
3. Из оставшейся части таблицы снова выбирают наименьшую стоимость и процесс продолжается до тех пор, пока все запасы не будут вывезены, а потребности удовлетворены;
4. Рассчитывают транспортные расходы: сумма произведений количества перевезенной продукции на стоимость для занятых клеток.

П. 2 Алгоритм метода Фогеля.

1. В каждой строке находят разность между двумя наименьшими стоимостями и записывают ее около соответствующей строки справа;
2. В каждом столбце находят разность между двумя наименьшими стоимостями и записывают ее под соответствующим столбцом;
3. Среди всех полученных разностей находят максимальную и распределяют объем перевозки в клетку строки или столбца с наименьшей стоимостью;
4. Исключают из рассмотрения строку или столбец с распределенными поставками и возвращаются к пункту 1. Процесс продолжается до тех пор, пока все запасы не будут вывезены, а потребности удовлетворены;
5. Когда план построен, рассчитываются транспортные расходы.

П.3 Алгоритм метода двойного предпочтения.

1. В таблице 9 в каждом столбце отмечают галочкой клетку с наименьшей стоимостью и в каждой строке отмечают галочкой клетку с наименьшей стоимостью;
2. В клетки с двумя галочками записывают максимально возможные объемы перевозок, каждый раз, исключая соответствующий столбец или строку;
3. Распределяют перевозки по клеткам с одной галочкой;
4. В оставшейся части таблицы перевозки распределяют в клетки с наименьшей стоимостью.
5. Когда план построен, рассчитываются транспортные расходы.

П.4. Алгоритм метода северо-западного  угла.

1. Пользуясь таблицей 9 распределяют груз, начиная с левой верхней, условно называемой северо-западной, клетки (1,1). Необходимо удовлетворить потребности В₁ за счет поставщика А₁;
2. а). Если b₁>a₁, в клетку (1,1) записывают a₁ и строку 1 вычеркивают из рассмотрения;

b). Если a₁>b₁, в клетку (1,1) записывают b₁ и столбец 1 вычеркивают из рассмотрения;

3. а). Если b₁>a₁, ∆= b₁ - a₁ – неудовлетворенные потребности. Спускаются на клетку вниз и сравнивают ∆ с a₂;

b). Если a₁>b₁, ∆=a₁ - b₁ – не вывезенные запасы. Двигаются по строке вправо  и сравнивают ∆ с b₂;

4. Необходимо вернуться к пункту 2;
5. Рассчитываются транспортные расходы.

П.5. Алгоритм метода потенциалов.

1. проверяется тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой;
2. находится опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшей стоимости;
3. проверяем план (таблицу) на удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью « 0 »;
4. для опорного плана определяются потенциалы u_i и v_j, соответствующие базисным клеткам, по условию:

u_i + v_j = c_ij

Таких уравнений будет  m + n - 1 , а переменных будет m + n. Для их определения одну из переменных полагают равной любому постоянному значению. Обычно принимают u₁ = 0.     

После этого для небазисных клеток опорного плана определяются оценки ,

где

При этом если £0, то опорный план оптимален, если же среди окажется хотя бы один положительный элемент, то опорный план можно улучшить.

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

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

Каждый цикл имеет четное число вершин, одна из которых в  клетке с небазисной переменной, другие вершины в клетках с базисными  переменными. Клетки отмечаются знаком «+», если перевозки в данной клетке увеличиваются и знаком «–» в противном случае. Цикл начинается и заканчивается на выбранной небазисной переменной и отмечается знаком «+». Далее знаки чередуются.

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

Цена цикла – это стоимость перевозки единицы продукта по циклу с учетом знаков вершин.

Улучшение опорного плана  осуществляется путем нахождения цикла  с отрицательной ценой.

5. Если критерий оптимальности не выполняется, то переходим к следующему шагу. Для этого:

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

б) составляется цикл пересчета;

в) находится число перерасчета  по циклу: число X=min{X_ij}, где X_ij - числа в заполненных клетках со знаком « - »;

г) составляется новая таблица, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла;

6. Возвращаются к пункту 3 и т.д.
7. Через конечное число шагов (циклов) обязательно приходят к ответу, так как транспортная задача всегда имеет решение.

 

 

 

Тест

1. «…» - это область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.

 

а) динамическое программирование;

б) линейное программирование; +

 

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

 

а) метод анализа ;+

б) метод искусственного базиса;

в) симплексный метод;

г) графический метод;

3. Транспортная задача имеет закрытую транспортную модель, когда:

      а) суммарное предложение больше суммарного спроса;

      б) суммарное предложение меньше суммарного спроса;

      в) суммарное предложение равно суммарному спросу; +

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

       а) положительным;

     б) отрицательным;

     в) оптимальным; +

5. Неповторяющиеся переменные называются:

    а) вспомогательными;

    б) базисными;  +

6. Повторяющиеся переменные называются:

     а) вспомогательными; +

     б) базисными;

7.        «. . .» - это наилучший с точки зрения выбранного критерия вариант развития экономики в целом или отдельного хозяйственного объекта. На уровне народного хозяйства разработку «. . .» можно представить, как выбор одного из ряда допустимых вариантов этого плана, и как процесс согласования планов (условно-оптимальных), полученных при решении отдельных моделей.

        а)  оптимальный план; +

        б)  допустимый план;

8. При решении задачи на max функции симплекс-методом план становится оптимальным тогда, когда коэффициенты при всех вспомогательных переменных будут:

       а) положительные; +

       б) отрицательные;

       в) равны нулю;

9. Улучшение опорного плана осуществляется путем нахождения цикла с

«. . .» ценой.

а) положительной;

б) отрицательной ; +

10. Транспортная задача называется «…», если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения

а) открытой;

б) закрытой; +

 

 

 

 

 

Задачи

Задача №1 

Для изготовления трех видов  изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования указаны в табл. 1. В ней же указан общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия каждого вида.

Таблица 1

Тип оборудования	Затраты времени  (станко-часы)   на обработку одного изделия  каждого вида			Общий фонд рабочего времени  оборудования (часы)
	А	В	С
Фрезерное	2	4	5	120
Токарное	1	8	6	280
Сварочное	7	4	5	240
Шлифовальное	4	6	7	360
Прибыль (руб.)	10	14	12

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

 

Задача №2

 

Менеджер предприятия, изготавливающего два вида красок, описал исследователю  операций ситуацию, сложившуюся на производстве и рынке сбыта красок. Оказалось, что фабрика изготавливает  два вида красок: для внутренних и внешних работ. Обе краски поступают  в оптовую продажу. Для производства красок используются два исходных продукта – А и В. Максимально возможные  суточные запасы этих продуктов 6 и 8 тонн соответственно. Опыт показал, что суточный спрос на внешнюю краску никогда не превышает спрос на внутреннюю более чем на 1 тонну. Кроме того, установлено, что спрос на внешнюю краску никогда не превышает 2 тонны в сутки. Оптовые цены одной тонны красок сложилось следующим образом: 3 тысячи рублей на внешнюю краску и 2 тысячи рублей на внутреннюю.

Какое количество краски каждого  вида должна производить фабрика, чтобы  доход от реализации был максимальным?