Определение исходного опорного решения.

Пусть имеется таблица 1 исходных данных задачи.

Исходное опорное решение будем строить по так называемому правилу «северо-западного угла». Заполняем таблицу 1, начиная с левого верхнего угла, двигаясь далее или по строке вправо, или по столбцу вниз.

В клетку (1, 1) занесем меньшее из чисел а₁ и b₁,, т.е. x₁₁ =min{a₁,b₁}.

Если, a₁ >b₁,,то x₁₁ = b₁, и первый столбец "закрыт", т.е. потребности первого потребителя удовлетворены полностью. Двигаемся далее по первой строке, записывая в соседнюю клетку (1,2) меньшее из чисел a₁-b₁ и, т.е. x₁₂ =min{a₁-b₁, b₂}.

Таблица 1

 

 

Если же b₁ > a₁, то аналогично "закрывается" первая строка и далее переходим к заполнению соседней клетки (2,1), куда заносим x₂₁ = min { a₂, b₁ – a₁,}. Будем продолжать этот процесс до тех пор, пока на каком-то этапе не исчерпаются все ресурсы а_i и потребности b_j.

Пример 1. В трех пунктах отправления (на складах) A₁, А₂, A₃ находится соответственно 100, 80, 120 т горючего. В пункты B₁, В₂, В₃ требуется доставить соответственно 60,140,100 т горючего. Стоимость перевозки тонны горючего из пункта A₁ в пункты В₁, В₂, В₃ составляют соответственно 4, 5, 1 ден. ед., из пункта А₂ - 6, 3, 4 ден. ед.,а из пункта А₃ - 1,2,4 ден. ед. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была минимальной.

Построим вначале исходный опорный план по правилу «северо-западного угла». Запишем исходные данные в таблицу 2.

Таблица 2

 

Заполнение начнем с клетки (1,1): х₁₁ = min{60,100}= 60, первый столбец закрыт. Переходим к клетке (1,2): х₁₂ = min {100-60,140}= 40, первая строка закрыта; далее переходим клетке (2, 2): х₂₂ = min{l40 - 40,80} = 80, вторая строка закрыта; переходим к клетке (3,2): х₃₂ = min {140-120,120}= 20, второй столбец закрыт. Наконец, заполняем клетку (3,3), куда заносим x₃₃ = min{120 -20,100}= 100. Поскольку остатки по строке и столбцу равны, исходное опорное решение построено. Этому плану соответствуют затраты в количестве F=60*4 + 40*5+80*3 + 20*2 + 100*4 = 1120ден.ед.

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

Применяют также прием «минимального элемента», в котором учитываются величины с_ij. В этом случае построение исходного базисного плана начинаем с клетки с наименьшей величиной с_ij, в данном примере с клетки (1,3) таблицы 3, где с₁₃ = 1.

Таблица 3

 

 

В эту клетку заносим x₁₃ = min { a₁,b₃ } = min {100,100}= 100. Остатки по строке и столбцу записываем в соответствующие клетки строки и столбца остатков. Строка а₁ и столбец b₃ закрыты. Теперь переходим к клетке (3, 1), так как с₃₁ = 1 и является наименьшим. Сюда заносим х₃₁ =min {60,120} =60 и закрываем столбец b₁. Переходим к клетке (3, 2), в которую заносим x₃₂ = min {120-60,140}= 60 и закрываем строку а₃. Наконец, переходим к клетке (2, 2), куда заносим х₂₂ =min{l40-60,80}=80 и закрываем столбец b₂ •

Получен другой вариант исходного опорного решения (плана), при котором затраты

F = 1*100+ 3*80+60*1 + 60*2 = 520 ден. ед., т.е. сумма затрат ближе к оптимальным.

Клетки таблицы 1, в которых содержатся ненулевые х_ij называют занятыми клетками. Ясно, что число занятых клеток в плане, построенном по методам «северо-западного угла» или «минимального элемента» не превосходит т+п -1.

2. Построение последовательности итераций, приводящих к оптимальному решению. Имея исходное опорное решение (опорный план), перейдем теперь к построению новых опорных решений, которые улучшают друг друга. Для этого применим метод потенциалов. После построения исходного опорного плана все переменные разбиты на две группы: х _kе –базисные, х_pq -свободные.

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

 

 

Для нахождения коэффициентов δ _pq при свободных переменных сопоставим каждому пункту отправления A_i некоторую величину α_i, , называемую потенциалом пункта А_i, и каждому пункту потребления (назначения) В_j. величину β_j - потенциал пункта В_j. Свяжем эти величины равенством

α_к +β_e = с_ке,

где с_ке - стоимость перевозки одной тонны груза из пункта А_k в пункт В_е. Доказывается, что совокупность уравнений α_к + β_e = с_ке, составленных для всех базисных переменных, будет составлять совместную систему линейных уравнений, причем значение одной из переменных (или даже нескольких) можно задавать произвольно, и тогда значения остальных находятся из системы однозначно. Пусть для свободных переменных с’_pq =α_p +β_q, назовем с’_pq косвенной стоимостью в отличие от данной стоимости с _pq. Тогда коэффициенты при свободных переменных в соотношении (5) определяются с помощью равенств δ _pq = с_pq - с’_pq

Если все величины δ _pq неотрицательны, то исходное решение является оптимальным. Если же среди них имеются отрицательные, то переходим к следующему базису путем увеличения члена с отрицательным коэффициентом, оставляя другие переменные равными нулю. Используем сформулированные положения и продолжим решение примера 1. Возьмем исходный базисный план, построенный по методу минимального элемента:

х₁₁ =0, х₁₂ =0, х₁₃ =100, х₂₁ =0, х₂₂ =80, x₂₃ = 0, х₃₁= 60, х₃₂ = 60, х₃₃ = 0, F=520.

Для нахождения потенциалов нужно решить для занятых клеток систему уравнений:

α₁ + β ₃ = 1,

α₂+β₂= 3,

α₃ + β ₁ = 1,

α₃ + β₂ = 2.

Значения двух неизвестных зададим произвольно, например α₁ =0, β ₁ = 0.

Тогда

 

α₁ =0

α₂ = 2.

α ₃ = 1

β ₁ = 0

β ₂ =1

β₃ = 1

Далее вычисляем косвенные стоимости для незанятых клеток с’_pq:

с’₁₁ = α₁ + β ₁ = 0,

с’₁₂ = α_l+ β₂=l,

с’₂₁ = α ₂+ β ₁ =2,

с’₂₃ = α ₂ + β ₃ = 3.

с’₃₃ = α ₃ + β ₃ = 2

Подсчитаем теперь разности δ _pq = с_pq - с’_pq

δ ₁₁ =4-0 = 4,

δ ₁₂ =5-1 = 4,

δ ₂₁ =6-2=4,

δ ₂₃ =4-3 = 1.

δ ₃₃ =4-2 = 2

Значит, выражение f через свободные переменные имеет вид F=520 + 4*х₁₁ + 4*х₁₂ + 4*х₂₁ + 1*х₂₃+ 2*х₃₃

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

Решим эту же задачу при условии, что исходное решение получено по правилу «северо-западного угла»,

т.е. х₁₁=60, х₁₂=40, х₁₃ =0, x₂₁ = 0, x₂₂ =80, x₂₃ =0, x ₃₁ =0, х₃₂ =20, х₃₃ =100, F = 1120.

Для нахождения потенциалов нужно решить систему для занятых клеток:

α₁ + β ₁ =4,

α₁ + β ₂ = 5,

α ₂+ β ₂ = 3,

α ₃+ β ₂ = 2,

α ₃ + β₃ =4.

Полагая α₁ = 0, получаем β ₁ =4, β ₂ =5, α ₂ = -2, α ₃ = -3, β ₃ = 7.

Вычисляем косвенные стоимости для незанятых клеток с’_pq (с’₁₃, с’₂₁, с’₂₃, с’₃₁)

с’₁₃ = α₁+β₃ = 7

с’₂₁ = α ₂ +β ₁ = 2

с’₂₃ = α ₂ +β₃ = 5

с’₃₁ = α ₃ +β ₁ = 1

Подсчитаем разности δ _pq = с_pq - с’_pq

δ ₁₃ =1- 7 =-6

δ ₂₁ =6- 2 = 4

δ ₂₃ =4- 5 =-1

δ ₃₁ =1- 1 =0

Следовательно, выражение F через свободные переменные имеет вид

F = 1120 - 6*x ₁₃ + 4* x ₂₁ -1*x ₂₃ + 0* x ₃₁

Среди коэффициентов при переменных в правой части есть отрицательные, например, при х₁₃, следовательно, можно попытаться уменьшить F, увеличив х₁₃ и сохранив при этом нулевые значение х₂₁ и х₂₃. Положим х₁₃ = λ. Поскольку суммы значений неизвестных по строкам и столбцам должны остаться неизменными, нужно произвести следующий балансовый пересчет:

 

 

Добавление λ к х₁₃ компенсируется вычитанием λ из х₁₂, а это в свою очередь.—прибавлением λ к х₃₂ и т.д. до тех пор, пока не вернемся обратно к х₁₃.. Обходя клетки по пунктирной ломаной линии, в одной из вершин которой находится свободная переменная х₁₃, а в остальных вершинах - базисные переменные, получим так называемый цикл пересчета (ломаную называют циклом), отвечающий свободной клетке х₁₃. Как видно из таблицы λ можно увеличить до λ = 40, тогда получим второе решение:

 

 

т.е. х₁₁ = 60, х₁₂=0, х₁₃= 40, x₂₁= 0, x₂₂== 80, х₂₃=0, х₃₁ =0, х₃₂ = 60, х₃₃ = 60. Значение функции для него составит

F = 4*60 +1*40 + 3*80+2*60+4*60 = 880, т.е. получим затраты ближе к оптимальным. Проверим полученный план на оптимальность методом потенциалов. Для нахождения потенциалов нужно решить систему:

α₁ + β ₁ =4, α₁ + β ₃ = 1, α ₂+ β ₂ = 3, α ₃+ β ₂ = 2, α ₃ + β₃ =4.

Полагая α₁ = 0, получаем β ₁ =4, β ₃ =1, α ₂ = 4, α ₃ = 3, β ₂ = -1.

α₁ = 0

α ₂ = 4

α ₃ = 3

β ₁ =4

β ₂ = -1

β ₃ =1

Вычисляем косвенные стоимости с’_pq (с’₁₂, с’₂₁, с’₂₃, с’₃₁)

с’₁₂ = α₁+β₂ = -1

с’₂₁ = α ₂ +β ₁ = 8

с’₂₃ = α ₂ +β₃ = 5

с’₃₁ = α ₃ +β ₁ = 7

Подсчитаем теперь разности δ _pq = с_pq - с’_pq

δ ₁₂ =5-(-1)=6

δ ₂₁ =6-8= -2

δ ₂₃ =4-5=-1

δ ₃₁ =4-7=-3

Следовательно, выражение F через свободные переменные имеет вид F = 1120 + 6*x ₁₂ - 2 * x ₂₁ -1*x ₂₃ -3 * x ₃₁.

Среди коэффициентов при переменных в правой части есть отрицательные, следовательно, можно уменьшить F.

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

60- λ		40+ λ
+ λ		60- λ

Добавление λ к х₁₃ компенсируется вычитанием λ из х₁₃, а это в свою очередь.— прибавлением λ к х₃₁ и т.д. до тех пор, пока не вернемся обратно к х₁₃. Обходя клетки по ломаной линии, в одной из вершин которой находится свободная переменная х₃₁, а в остальных вершинах - базисные переменные, получим цикл пересчета, отвечающий свободной клетке х₃₁. Как видно из таблицы, λ можно увеличить до λ = 60, тогда получим третье решение:

		100
	80
60	60

т.е. х₁₁ = 0, х₁₂=0, х₁₃= 100, x₂₁= 0, x₂₂== 80, х₂₃=0, х₃₁ =60, х₃₂ = 60, х₃₃ = 0. Значение функции для него составит F = 1*100 +1*60 + 3*80+2*60 = 520, т.е. получим затраты еще ближе к оптимальным. Проверим полученный план на оптимальность методом потенциалов. Для нахождения потенциалов нужно решить систему:

α₁ + β ₃ =1, α₂ + β ₂ = 3, α ₃+ β ₁ = 1, α ₃+ β ₂ = 2.

Полагая α₁ = 0 и β ₁ =1 получаем β ₃ =1, α ₃ = 1, β ₂ = 1, α ₂ = 2.

α₁ = 0

α ₂ = 2

α ₃ = 1

β ₁ =0

β ₂ = 1

β ₃ =1

Вычисляем косвенные стоимости с’_pq (с’₁₁, с’₁₂, с’₂₁, с’₂₃, с’₃₃)

с’₁₁ = α₁+β₁ = 0+0=0

с’₁₂ = α ₁ +β ₂ = 0+1=1

с’₂₁ = α ₂ +β₁ = 2+0=2

с’₂₃ = α ₂ +β ₃ = 2+1=3

с’₃₃ = α ₃ +β ₃ = 1+1=2

Подсчитаем теперь разности δ _pq = с_pq - с’_pq

δ ₁₁ =4-0=4

δ ₁₂ =5-1= 4

δ ₂₁ =6-2=4

δ ₂₃ =4-3=1

δ ₃₃ =4-2=2

Следовательно, выражение F через свободные переменные: F = 520 + 4*x ₁₁ + 4 * x ₁₂ +4*x ₂₁ +1 * x ₂₃. +2 * x ₃₃.

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

1.Для имеющегося опорного плана вычисляем функцию . Полагаем F = δ₀.

2. Используя уравнение α _i + β _j = с _{i j} для занятых клеток, определяем потенциалы α_i и β_j всех пунктов отправления A_i и назначения В_j.

3. Через полученные α _i и β_j вычисляем для свободных клеток косвенные стоимости с’ _ij =α_i +β_j.

4. Находим для свободных клеток разности заданной и косвенной стоимостей δ _ij = с_ij - с’_ij

5. Выбираем свободную клетку, для которой разность δ _ij отрицательна, это соответствует элементу с отрицательным коэффициентом при свободной переменной в правой части функции F = δ₀.+ (если таких переменных несколько, то берем ту из них, где отрицательный коэффициент — наибольший).

6. Для выбранной в п. 5 переменной находим соответствующий ей цикл пересчета и производим сдвиг по этому циклу. Этот сдвиг приводит к новому опорному решению.

Указанные операции 1-5 повторяем до тех пор, пока не получим оптимальный базисный план, т.е. неотрицательные коэффициенты при свободных переменных в правой части линейной функции F.

Задания

Для выполнения задания студенту предлагается выбрать вариант по номеру своей зачетной книжки, разделив его на 5. Остаток от деления будет соответствовать номеру варианта. Например, 87386 делим на 5. Получаем остаток 1, т.е. вар.1.

Задание 1.

Вариант 0. На предприятии производится два вида продукции на оборудовании, установленном в трех цехах. Известны нормы использования оборудования для производства единицы продукции в каждом цехе, количество установленного оборудования в каждом цехе, прибыль от производства единицы продукции каждого вида. Построить математическую модель задачи для определения оптимального плана производства продукции по критерию максимизации прибыли. Данные задачи сведены в таблицу:

Номер цеха	Нормы использования оборудования для производства единицы продукции, шт.	Количество установленного оборудования, шт.
1 вида	2 вида
		-
Прибыль на ед. продукции, руб.

Вариант 1. Чулочно-носочная фирма производит и продает два вида товаров: мужские носки и женские чулки. Фирма получает прибыль в размере 10 руб. от производства и продажи одной пары чулок и в размере 5 руб. от производства и продажи одной пары носков. Производство каждого изделия осуществляется на трех участках. Затраты труда (в у.е.) на производство одной пары указаны в следующей таблице для каждого участка:

Участок производства	Чулки	Носки

Руководство рассчитало, что в следующем месяце фирма ежедневно будет располагать следующими ресурсами рабочего времени на каждом из участков: 350 у.е на участке 1; 392 у.е. на участке 2 и 408 у.е. ч на участке 3. Построить математическую модель задачи для определения оптимального плана производства продукции по критерию максимизации прибыли.

Вариант 2. Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 1 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется в течении 2 часов, оборудование второго типа – 3 часов, оборудование третьего типа – 1 час. На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часа, оборудование второго типа – 60 часов, оборудование третьего типа – 50 часов. Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы. Построить математическую модель задачи для определения оптимального плана производства продукции по критерию максимизации прибыли.

Вариант 3. Для производства двух видов изделий А и В предприятие использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице. В ней же указана прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое может быть использовано предприятием. Построить математическую модель задачи для определения оптимального плана производства продукции по критерию максимизации прибыли.

Вид сырья	Нормы расхода сырья в кг на 1 изделие
А	В
I
II
III
Прибыль на ед. продукции, руб.

Вариант 4. Фирма производит две модели продукции Р₁ и Р₂. В их производстве используется три вида сырья: S₁, S₂, S₃. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также вели­чина прибыли, получаемой от реализации единицы продукции, приведены в таблице:

Вид сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
Р1	Р2
S1
S2
S3
Прибыль от единицы продукции в руб.

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

Задание 2.

Решить задачу линейного программирования, поставленную в задании 1, графическим способом.

Задание 3.

Перейти от стандартной формы задачи линейного программирования, выполненной в задании 1, к канонической.

Задание 4.

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

Задание 5.

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

 

 

Склады	Магазины	Запасы товара на складе
В1	В2	В3	В4
Стоимость перевозки 1 т угля
А1
А 2
А3
Потребности магазина в товаре

Вариант 1. На трёх складах хранится каменный уголь соответственно в количествах 520, 480 и 1000 тонн. Этот уголь нужно доставить в пять пунктов потребления соответственно в количествах 800, 750, 250, 200 и 300 тонн. В таблице приведены стоимости перевозок одной тонны угля от каждого склада ко всем пунктам потребления. Составить план перевозки угля так, чтобы общие затраты на перевозки были минимальными.

Склады	Пункты потребления угля
В1	В2	В3	В4	В5
А1
А2
А3

Вариант 2. Имеются три пункта поставки однородного груза А₁, А₂, А₃ и пять пунктов В₁, В₂, В₃, В₄, В₅ потребления этого груза. На пунктах А₁, А₂, А₃ находится груз в количествах 90, 70, 110 тонн. В пункты В₁, В₂, В₃, В₄, В₅ требуется доставить соответственно 50, 60, 50, 40, 70 тонн груза. Расстояния в сотнях километрах между пунктами поставки и потребления приведены в таблице. Найти такой план перевозок, при котором общие затраты будут минимальными.

Пункты поставки	Пункты потребления
В1	В2	В3	В4	В5
А1
А2
А3

Вариант 3. Сталеплавильная компания располагает тремя заводами М₁, М₂, М₃, способными произвести за некоторый промежуток времени 50, 30 и 20 тыс. т стали соответственно. Свою продукцию компания поставляет четырем потребителям С₁, С₂, С₃, С₄, потребности которых составляют соответственно 12, 15, 25, 36 тыс. т стали. Стоимость производства и транспортировки 1 тыс. т стали с различных заводов различным потребителям в таблице. Найти объемы производства и план перевозок, при котором общие затраты будут минимальными.

Завод	Потребитель
С1	С2	С3	С4
М1 М2 М3

Вариант 4. Компания контролирует 3 фабрики F₁, F₂ и F₃, способные произвести 50, 25 и 25 тыс. изделий еженедельно. Она заключила договоры с 4 заказчиками С₁, С₂, С₃, С₄, которым требуется еженедельно 15, 20, 20, 30 тыс. изделий. Стоимости производства и транспортировки 1 тыс. изделий заказчикам с фабрик приведены в таблице. Определить объемы производства и распределение для каждой фабрики, минимизирующие общую стоимость.

Фабрика	Заказчик
С1	С2	С3	С4
F1 F2 F3