Решение

1. Введем логическую переменную х_j ={ 1, если Р_j – принять,

0, если отклонить

2. Цель - максимизировать суммарных эффект от инвестиций, Общий объем возможных инвестиций ограничен 60 млн.грн.

3. F (x)= 48х₁+55х₂ + 45х₃ +39х₄ → max

22 х₁ + 25х₂ +20х₃ +17х₄ ≤ 60

х₁, х ₂ , х_3, х₄ ≥ 0 (условие неотрицательности)

4.

2.2.

В транспортной задаче (Т –задаче) необходимо составить оптимальный план_, т.е. найти такие значения объема перевозок грузов х_ij от поставщиков А_i к потребителям В _j , чтобы:

1- вывести все грузы от поставщиков

2 – удовлетворить заявки каждого потребителя

3 – обеспечить минимальные транспортные расходы С_ij на перевозку грузов.

Все исходные данные Т- задачи можно записать в виде таблицы.

Пункты отправления (поставщики)	Пункты назначения (потребители)				Запасы ai
	B1	B2	…….	Bn
А1	C11 х11	C12 х12		C1n х1n	a1
А2	C21 х21	C22 х22		C2n х2n	a2
….					…..
Аm					am
bi	b1	b2		bn	Σ bi Σ ai

Целевая функция Т-задачи:

Условие, необходимое для разрешимости Т-задачи, сводиться к балансу: Σ a_i = Σ b_{i .} Такие задачи называются закрытыми (в противном случае называются открытыми).

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

Алгоритм метода рассмотрим на примере.

Пример. На три базы P, Q, R поступил однородный груз в количествах 9,4 и 8 единиц. Этот груз требуется перевезти в три магазина А,В,С в количествах 3,5 и 6 единиц. Составьте оптимальный план транспортировки грузов, так чтобы общая стоимость транспортировки была минимальной. Стоимость транспортировки единицы груза приведены в табл.

поставщики	Пункты назначения (потребители)				Запасы
	А	B	С	Фиктивный
P	10	20	5	0	9
Q	2	10	8	0	4
R	1	20	7	0	8
Потребность магазина	3	5	6	7	Σ 21

1. Проверим сбалансированность транспортной задачи, для этого необходимо чтобы

Σ a_i =9+4+8=21 b_i =3+5+6=14 (открытый тип задачи)

Поэтому вводим «фиктивный»магазин, его потребность будет равна 21-14=7 изделий и предполагается, что затраты транспортировки равны 0.

2. Применим метод «минимальной стоимости».

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

-производится корректировка оставшихся объемов предложения и потребностей.

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

Поставщики	Пункты назначения (потребители)				Запасы
	А	B	С	Ф
P	10	20	5	0	9
Q	2	10	8	0	4
R	1	20	7	0	8
Потребность магазина	3	5	6	7	Σ 21

Количество перевозок должно быть равно m+n –1 =4+3–1=6

Целевая функция первоначального плана:

2. Одним из методов проверки первоначального плана на оптимальность – является метод потенциалов.

Потенциалами называется система чисел, приписанных соответственно каждой строке i и каждому столбцу j.

Экономическая сущность потенциалов: потенциал U_i можно принять условно за цену товару в пункте его производства, потенциалом V_j можно принять условно за цену товару в пункте его потребления.

V_j = U_i + С_ij

Строим систему потенциалов. Начинаем с того, что строке 1 присваиваем потенциал U₁=0.

поставщики	U Vj i	потребители				Запасы
		А	B	С	Ф
P		10 –	20 –	5 2	0 7	9
Q		2 –	10 4	8 –	0 –	4
R		1 3	20 1	7 4	0 –	8
Потребность магазина		3	5	6	7	Σ 21

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

U_i + С_ij ≥ V_j

U₁ + С₁₁ ≥ V₁ 0+10≥-1

U₁ + С₁₂ ≥ V₂ 0+20≥18

U₂ + С₂₁ ≥ V₁ 8+2≥-1

U₂ + С₂₃ ≥ V₃ 8+8≥5

U₂ + С₂₄ ≥ V₄ 8+0≥0

U₃ + С₃₄ ≥ V₄ -2+0≥0 (условие не выполняется, план не оптимальный).

Для оптимизации плана необходимо переместить перевозку в квадрант 3.4. Перемещение производиться таким образом, чтобы по отношению к выбранному квадранту образовать связку. Для этого необходимо провести замкнутую ломаную линию, в которой одной из вершин многоугольника является свободный квадрат, а остальные вершины находятся в занятых квадратах. Затем присваиваем знаки «+» и «–» начиная со свободного квадрата. Из квадратов со знаком «–» перемещаем перевозки в квадраты со знаком «+». Перемещается наименьшее количество, которое находится в квадратах связки со знаком «–».

поставщики	U Vj i	потребители				Запасы
		А	B	С	Ф
P		10 –	20 –	5 2	0 7	9
Q		2 –	10 4	8 –	0 –	4
R		1 3	20 1	7 4	0 –	8
Потребность магазина		3	5	6	7	Σ 21

+

-

+

– е перемещаем число «___»

Строим новую систему потенциалов и проверяем план на оптимальность.

поставщики	U Vj i	потребители				Запасы
		А	B	С	Ф
P		10 –	20 –	5 6	0 3	9
Q		2 –	10 4	8 –	0 –	4
R		1 3	20 1	7 –	0 4	8
Потребность магазина		3	5	6	7	Σ 21

Для всех свободных квадратов выполняться условие: U_i + С_ij ≥ V_j , поэтому план оптимальный.

Целевая функция оптимального плана:

Ответ: 6 изделий перевозятся с базы P в магазин С., 3 изделия остаются на базе P., 4 изделия перевозятся с базы Q в магазин В, с базы R перевозятся 3 изделия в магазин А, 1 изделие в магазин В, 4 изделия остаются на базе R.