Транспортные задачи (на примере КПУП "Хойникский сыродельный комбинат")

       С целью расширения рынка сбыта и увеличения объёмов  реализации, комбинат в очередной  раз расширяет ассортимент продукции кисломолочным фруктовым напитком с лактулозой трёх видов фасовки:

       -плёнка 0.5 кг. ;

       -полистироловые  стаканчики 0.4 кг. ;

       -полистироловые  стаканчики 0.2 кг.

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

        Информация о поставщиках КПУП "Хойникский сыродельный комбинат"

       Основными поставщиками молока являются 4 совхоза-комбината, расположенные в пределах Гомельской области на различном расстоянии от предприятия, а также население Хойникского района .

Алгоритм  и методы поиска решения

   В процедуре поиска решения Microsoft Excel используется алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University).

   Алгоритмы симплексного метода и метода «branch-and-bound» для решения линейных и целочисленных задач с ограничениями разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc.

Создание  модели для поиска решения

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

Постановка  задачи и оптимизация  модели с помощью  процедуры поиска решения

   1.   В меню Сервис выберите команду Поиск решения.

   Если  команда Поиск решения отсутствует  в меню Сервис, установите соответствующую  надстройку.

Инструкции

   2.  В поле Установить целевую ячейку введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.

   3. Чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение максимальному значению.

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

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

   4.  В поле Изменяя ячейки введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

   Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку Предположить.

       5.    В поле Ограничения введите все ограничения, накладываемые на поиск решения.

 Диалоговое  окно «Добавить ограничение» и «Изменить ограничение» 

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

         Ограничение - Служит для задания условия, которое накладывается на значения ячейки или диапазона, указанного в поле Ссылка на ячейку. Выберите необходимый условный оператор и введите ограничение ѕ число, формулу, ссылку на ячейку или диапазон ѕ в поле справа от раскрывающегося списка.

           Добавить- Нажмите на кнопку, чтобы, не возвращаясь в окно диалога Параметры поиска решения, наложить новое условие на поиск решения задачи.

   6.   Нажмите кнопку Выполнить.

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

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

   Пример  решения транспортной задачи на примере предприятия КПУП"Хойникский сыродельный комбинат":

      Совхозы А1, А2, А3  выделяют соответственно 30, 40 и 20 ц. Молока  для ежедневного снабжения цехов( В1, В2, В3, В4),выпускающих продукцию. Стоимость перевозки и потребности пунктов даны в таб. 2.

                                                                                                          Таб. 2.

Совхоз		Потребитель								Предназначено для вывоза
		В1		В2		В3		В4
А1		2		3		5		4		30
А2		3		2		4		1		40
А3		4		3		2		6		20
Потребность		20		25		35		10		90

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

  Выполнение:

1. Вносятся данные по издержкам из исходной таблицы в необходимый диапазон клеток.
2. Создаем на листе Exell таблицу.
3. В качестве исходных значений таблицы можно взять «0».

Совхоз	Потребитель				Предназначено для вывоза
	В1	В2	В3	В4
А1	2	3	5	4	30
А2	3	2	4	1	40
А3	4	3	2	6	20
Потребность	20	25	35	10	90
А1	0	0	0	0	0
А2	0	0	0	0	0
А3	0	0	0	0	0
Потребность	0	0	0	0	0

 

4. Чтобы сформировать формулы суммирования для ограничений, выделяем блок на одну строку и на один столбец больше блока решений  и выполняем Автосуммированние  на панели инструментов. В окаймляющие строку и столбец заносятся формулы суммирования по строкам и столбцам. Эти формулы будут использоваться для левых ограничений по потребителям и поставщикам в соответствии с таблицей.
5. Для функции вводим формулу «=СУММПРОИЗВ(массивы из двух таблиц) ».
6. Выбираем команду «Поиск решения». В окне «Поиск решения» вносим:

• Целевую ячейку (ссылка на ячейку с целевой функцией).

• Изменяя ячейки (ссылки на ячейки с ограничениями).
• Min.
• Ограничения.

Нажимаем  кнопку ОК, затем - «Выполнить».

Совхоз	Потребитель				Предназначено для вывоза
	В1	В2	В3	В4
А1	2	3	5	4	30
А2	3	2	4	1	40
А3	4	3	2	6	20
Потребность	20	25	35	10	90
А1	20	10	0	0	30
А2	0	15	15	10	40
А3	0	0	20	0	20
Потребность	20	25	35	10	90
MIN Z =	210

  Сохранить полученные результаты в виде отчета.

Отчет по решению задачи.
Target Cell (Min)
	Cell	Name	Original Value	Final Value
	$B$13	MIN Z= В1	0	210
Adjustable Cells
	Cell	Name	Original Value	Final Value
	$B$7	А1 В1	0	20
	$C$7	А1 В2	0	10
	$D$7	А1 В3	0	0
	$E$7	А1 В4	0	0
	$B$8	А2 В1	0	0
	$C$8	А2 В2	0	15
	$D$8	А2 В3	0	15
	$E$8	А2 В4	0	10
	$B$9	А3 В1	0	0
	$C$9	А3 В2	0	0
	$D$9	А3 В3	0	20
	$E$9	А3 В4	0	0
Constraints
	Cell	Name	Cell Value	Formula	Status	Slack
	$B$10	Потребность В1	20	$B$10=$B$6	Binding	0
	$C$10	Потребность В2	25	$C$10=$C$6	Binding	0
	$D$10	Потребность В3	35	$D$10=$D$6	Not Binding	0
	$E$10	Потребность В4	10	$E$10=$E$6	Not Binding	0
	$F$7	А1 Предназначено  для вывоза	30	$F$7=$F$3	Not Binding	0
	$F$8	А2 Предназначено для вывоза	40	$F$8=$F$4	Not Binding	0
	$F$9	А3 Предназначено  для вывоза	20	$F$9=$F$5	Not Binding	0
	$B$7	А1 В1	20	$B$7>=0	Not Binding	20
	$C$7	А1 В2	10	$C$7>=0	Not Binding	10
	$D$7	А1 В3	0	$D$7>=0	Binding	0
	$E$7	А1 В4	0	$E$7>=0	Binding	0
	$B$8	А2 В1	0	$B$8>=0	Binding	0
	$C$8	А2 В2	15	$C$8>=0	Not Binding	15
	$D$8	А2 В3	15	$D$8>=0	Not Binding	15
	$E$8	А2 В4	10	$E$8>=0	Not Binding	10
	$B$9	А3 В1	0	$B$9>=0	Binding	0
	$C$9	А3 В2	0	$C$9>=0	Binding	0
	$D$9	А3 В3	20	$D$9>=0	Not Binding	20
	$E$9	А3 В4	0	$E$9>=0	Binding	0
	$B$7	А1 В1	20	$B$7=integer	Binding	0
	$C$7	А1 В2	10	$C$7=integer	Binding	0
	$D$7	А1 В3	0	$D$7=integer	Binding	0
	$E$7	А1 В4	0	$E$7=integer	Binding	0
	$B$8	А2 В1	0	$B$8=integer	Binding	0
	$C$8	А2 В2	15	$C$8=integer	Binding	0
	$D$8	А2 В3	15	$D$8=integer	Binding	0
	$E$8	А2 В4	10	$E$8=integer	Binding	0
	$B$9	А3 В1	0	$B$9=integer	Binding	0
	$C$9	А3 В2	0	$C$9=integer	Binding	0
	$D$9	А3 В3	20	$D$9=integer	Binding	0
	$E$9	А3 В4	0	$E$9=integer	Binding	0