Контрольная работа: Метод потенциалов для решения транспортной задачи в матричной форме. Задача оптимального распределения ресурсов
х5 = х2 + x3 – 25 + 3х2 – 4x3 + 30
q = x2 + х3 – 25 + 2х2 + 3x3
x1 = –x2 – х3 + 25 (1)
х4 = –5x2 + х3 + 40 (2)
х5 = 4х2 – 3x3 + 5 (3)
q = –x2 + 4х3 – 25 (4)
Выразим х2 из второго ограничения и подставим его выражение в первое и третье ограничения, а также в выражение для целевой функции:
5x2 = х3 – х4 + 40
х2 = 0,2х3 – 0,2х4 + 8
x1 = –0,2x3 + 0,2х4 – 8 –x3 + 25
х2 = 0,2х3 – 0,2х4 + 8
х5 = 0,8х3 – 0,8x4 + 32 –3x3 + 5
q = –0,2x3 + 0,2х4 – 8 + 4х3 – 25
x1 = –1,2x3 + 0,2х4 + 17
х2 = 0,2х3 – 0,2х4 + 8
х5 = –2,2х3 – 0,8x4 + 37
q = 3,8x3 + 0,2х4 – 33
В выражении для функции q оба неизвестных входят со знаком «+». Поэтому можно утверждать, что найден оптимальный план: х3 = х4 = 0. Подставив эти значения в последнюю систему ограничений, получим и остальные неизвестные:
х1 = 17; х2 = 8; х5 = 37;
Оптимальное значение функции q = – 33, следовательно
f(x) = 33 млрд.руб.
Ответ: f(x) = 33 млрд.руб.
Задача №4
Метод динамического программирования для выбора оптимального профиля пути.
Задание:
Требуется найти оптимальную трассу участка железнодорожного пути между пунктами А и В, из которых второй лежит к северо-востоку от первого. Местность, по которой пройдет магистраль, является пересеченной и включает лесистые зоны, холмы, болота, реку. Поэтому стоимость строительства равных по длине участков пути может быть различной. Требуется так провести дорогу из А в В, чтобы суммарные затраты на сооружение участка были минимальны.
План прокладки пути разобьем на ряд возможных шагов, на каждом из которых стоимость строительства известна. Каждый шаг строительства является прокладкой пути между двумя рядом расположенными узлами. Все узлы пронумерованы, и в соответствии с номером варианта дана стоимость сооружения элемента пути между узлами.
Исходные данные – (вариант 67 ).
Решение: