Дадим геометрическое истолкование задачи, используя для этого её формулировку с ограничениями-неравенствами

x₁ + 2 x₂  32

3x₁ + 3x₂  60

3x₁ + x₂  50

x_i  0, i = 1,2.

F = 4x₁ + 2x₂ (max).

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

Ответ: план производства изделий А и В, обеспечивающий максимальную прибыль

денежных единиц от их реализации: изделий А - 15 штук и изделий В - 5 штук.

71 - 80. Имеются три пункта поставки однородного груза А₁, А₂, А₃ и пять пунктов В₁, В₂, В₃, В₄, В₅ потребления этого груза. На пунктах А₁, А₂, А₃ находится груз в количестве а_1, а₂, а₃ тонн. В пункты В₁, В₂, В₃, В₄, В₅ требуется доставить соответственно b₁, b₂, b₃, b₄, b₅ - тонн груза. Расстояния в сотнях километров между пунктами поставки и потребления приведены в матрице-таблице D= (d_ij):

Пункты поставки (базы – Б)	Пункты потребления (потребители – П)
	В1	В2	В3	В4	В5
А1	d11	d12	d13	d14	d15
А2	d21	d22	d23	d24	d25
А3	d31	d32	d33	d34	d35

Найти такой план перевозок, при котором общие затраты будут минимальными.

У к а з а н и е : 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое этот груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах;

2) для решения задачи использовать методы северо-западного угла и потенциалов.

7x.	90, 70, 110,
	50, 60, 50, 40, 70.

Решение. Согласно указанию 1) требуется минимизировать стоимость перевозок (суммарные затраты) S =  d_ijx_ij. Далее расстояние d_ij будем обозначать через c_ij и называть тарифом.

Первое базисное решение найдем по методу северо-западного угла.

П Б	50	60	50	40	70	i
90	7 50	1 40	7	4	9	0
70	4	3 20	2 50	1 0	5	2
110	5	6	8	6 40	2 70	7
j	7	1	0	-1	-5

В клетку с тарифом d₁₁ = c₁₁ = 7 помещаем наибольший возможный груз x = 50 , далее выбираем клетку с тарифом 1 и помещаем туда груз 40 и т.д. При этом следим за тем, чтобы на каждом шаге, кроме последнего, из рассмотрения выбывали только одна строка или столбец, в противном случае в одном из выбывающих рядов ( в строке или в столбце) ставим ноль в клетку с наименьшим тарифом ( в данном случае в клетку (2, 4) с тарифом 1 ставим 0).

Проверим является ли полученное базисное решение оптимальным с помощью метода потенциалов. Составим уравнения для всех базисных (загруженных) клеток:

c_ij = _i + _j (1)

Так как число уравнений m + n – 1 = 3 + 5 –1 = 7, а число потенциалов _i, _j равно m + n = 8, то пусть ₁ = 0. Далее находим потенциалы из следствий уравнений (1):

_j = c_ij - _i или _i = c_ij - _j.

Результаты заносим в таблицу. Далее находим алгебраические суммы тарифов s_ij для всех свободных клеток из уравнений:

s_ij = c_ij – (_i + _j ) (2)

(Запишем только s_{ij <} 0, если есть)

s₂₁ = 4 – (2+7)= - 5;

s₃₁ = 5 – (7+7)= - 9; s₃₂ = 6 – (7+1)= - 2.

Так как не все s_ij  0, то базисное решение не является оптимальным.

Выбираем клетку ( 3 , 1 ) с наименьшей из отрицательных алгебраических сумм тарифов - 9 и строим цикл пересчета для получения нового базисного решения.

Перераспределяемый груз x_ij = min ( 50; 20; 40 ) = 20

Запишем новое базисное решение в таблицу и проделаем процедуру пункта до тех пор пока не получим для всех свободных клеток s_ij  0.

П Б	50	60	50	40	70	i
90	7 30	1 60	7	4	9	0
70	4	3	2 50	1 20	5	-7
110	5 20	6	8	6 20	2 70	- 2
j	7	1	9	8	4

s₁₃ = 7 – (0+9)= - 2; s₁₄ = 4 – (0+8)= - 4;

П Б	50	60	50	40	70	i
90	7 10	1 60	7	4 20	9	0
70	4	3	2 50	1 20	5	-3
110	5 40	6	8	6	2 70	-2
j	7	1	5	4	4

Так как для всех свободных клеток s_ij  0, то полученное базисное решение является оптимальным.

Наименьшие суммарные затраты S_min =  c_ijx_ij = 10 · 7 + 60 · 1 + 20 · 4 + 50 ·2 + 20 · 1 + 40 · 5 + 70 · 2 = 670

Замечание. Данное решение не является единственным , так как клетка (2, 1 ) имеет

s₂₁ = 4 – (-3+7)= 0 .

- нулевая алгебраическая сумма тарифов.

С помощью цикла пересчета клетки (2, 1 ) можно получить еще одно оптимальное решение.

81 - 90. Дана задача выпуклого программирования. Требуется: