Контрольная по Методам оптимальных решений

Тема: Контрольная по Методам оптимальных решений

Раздел: Бесплатные рефераты по методам оптимальных решений

Тип: Контрольная работа | Размер: 161.95K | Скачано: 272 | Добавлен 13.11.14 в 19:16 | Рейтинг: 0 | Еще Контрольные работы

Вуз: Алтайский государственный аграрный университет

Год и город: Барнаул 2014

10.Классификация задач оптимального программирования

Задачи оптимального программирования классифицируют по следующим признакам.

Задачи по характеру взаимосвязи между переменными:

линейные (все функциональные связи в системе ограничений и функция цели – линейные функции);

нелинейные (наличие нелинейности в системе ограничений, функции цели).

Задачи по характеру изменения переменных:

непрерывные;

дискретные.

Задачи по учету фактора времени:

статические;

динамические.

Задачи по наличию информации о переменных:

задачи в условиях полной определенности (детерминированные);

задачи в условиях неполной информации (случай риска);

задачи в условиях неопределенности.

Задачи по числу критериев оценки альтернатив:

простые (однокритериальные), где экономически приемлемо использование одного критерия оптимальности;

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

11.Общая задача линейного программирования, её математическая формулировка

На практике наиболее широкое распространение получили экономические задачи, в которых условия производства и критерий оптимальности могут быть представлены в виде системы линейных уравнений и неравенств, в которые входят неизвестные переменные в первой степени (уравнения вида y = ax+ b) .

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

В теории линейного программирования разработаны эффективные методы нахождения оптимального плана согласно экстремальному значению целевой функции. Чтобы воспользоваться этими методами необходимо математически сформулировать (описать) условия и ограничения задачи.

Математическая формулировка общей задачи линейного программирования

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

n – количество переменных;

m – количество ограничений;

xj– неизвестные искомые переменные величины;

j – номер переменной, изменяющийся от 1 до n (j = 1, 2, …, n);

aij– коэффициенты при неизвестных величинах;

i – номер ограничения, изменяющийся от 1 до m (i = 1, 2, …, m);

bi– свободные члены уравнений и неравенств (заданные постоян-ные величины);

Z – целевая функция;

cj– коэффициенты при искомых переменных в целевой функции.

Тогда общую задачу линейного программирования можно математически сформулировать следующим образом:

Найти такое решение Х, то есть значения неизвестных xj (j = 1, 2, …, n), которое бы обеспечивало экстремальное значение кри-терия оптимальности, выраженного линейной функцией:

Z (Х) = c1x1 + c2x2 + …+ cnxnextr,

при соблюдении следующих m условий (линейных ограничений):  

 

Структурная форма записи задачи линейного программирования

Общую задачу линейного программирования можно записать в сжатой форме с помощью знака суммирования.

Найти экстремум функции:Z=  , при условиях:

 

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

целевая функция;

система ограничений;

условие неотрицательности искомых переменных величин.

29.Структурная модель задачи оптимизации производственно-отраслевой структуры предприятия.

Требуется составить оптимальный план, т.е. определить значение переменных xj, xkj, xi, xs,  xi, xh, при котором достигается максимум прибыли:

Z_max= x_h – x_i; hÎH, iÎI, где

j – индекс вида деятельности растениеводства или животноводства;

xj – размер j-го вида деятельности растениеводства или животноводства (посевные площади j-й культуры или поголовье j-го вида животных);

k – индекс групп кормов; k=K;

K – множество групп кормов;

хkj – добавка корма k–й группы сверх минимально необходимой нормы для j-го вида животных;

i – индекс вида ресурса;

xi – объем ресурса i-го вида, в том числе и материально-денежных затрат на производство товарной продукции;

xi – размер пополнения ресурса i-го вида (трансформация угодий, дополнительное привлечение рабочей силы);

s – индекс вида покупного корма или побочной продукции, используемой на корм;

xs – количество покупного корма s-го вида;

h – индекс стоимостного показателя;

xh – размер стоимостного результативного показателя (стоимость товарной продукции);

H – множество стоимостных показателей;

I – множество видов ресурсов, определяемых в процессе решения задачи.

Максимум целевой функции достигается при выполнении следующих ограничений.

1. По земельным ресурсам

Математическая запись условий:

 

где a_ij – потребность в i-м виде занимаемых угодий в расчете на единицу j-го вида растениеводства; B_i – объем ресурса i-го вида; N – множество видов деятельности растениеводства; x_i – размер пополнения ресурса j-го вида (в данном случае трансформация угодий); I – множество видов земельных угодий.

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

Для записи этой ситуации вводим обозначение переменных.

Посевные площади под отдельными видами культур, га:

х₁ – яровой пшеницей;

х₂ – ячменем;

х₃ – овсом;

х₄ – гречихой;

х₅ – картофелем;

х₁₅ – многолетними травами на сено;

Площади сенокосов и пастбищ, га:

х₁₆ – площадь естественных сенокосов;

х₁₇ – площадь культурных пастбищ;

х₂₄ – вспомогательная переменная площадь трансформируемых в пашню естественных пастбищ.

Ресурсы:

В₁ – пашня, га;

В₂ – площадь естественных сенокосов, га;

В₃ – площадь культурных пастбищ, га;

В₄ – площадь естественных пастбищ, га;

В₅ – площадь естественных пастбищ, определенная для трансформации в пашню, га;

В₆ – трудовые ресурсы хозяйства, всего в году, чел.-ч;

В₇ – то же, в мае, чел.-ч;

В₈ – то же, в августе и т.д., чел.-ч.

С помощью этих обозначений условия по использованию земельных угодий записывают следующим образом:

1) по использованию пашни х₁+х₂+,…,+х₁₅ ≤ В₁ + х₂₄;

2) по использованию естественных сенокосов х₁₆ ≤ В₂;

3) по использованию культурных пастбищ х₁₇ ≤ В₃;

4) по использованию естественных пастбищ х₁₀ ≤ В₄ – х₂₄;

5) по трансформируемой площади естественных пастбищ х₂₄ ≤ В₅.

Соответственно вводят ограничения по возможной аренде земли. Эти ограничения составляют подматрицу земельных угодий.

2. Ограничения по трудовым ресурсам.

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

 

где t – индекс периода использования трудовых ресурсов; Т - множество периодов; a_ij – норма затрат труда в расчете на единицу j-го вида деятельности в t-м периоде; В_i^t – наличие трудовых ресурсов в t-м периоде; х_i^t - наличие привлекаемых трудовых ресурсов в t-м периоде.

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

6) по годовому использованию трудовых ресурсов а₆₁х₁ + а₆₂х₂ + … + а_{6 21}х₂₁ ≤ В₆ + х₂₅,

где х_1....х₂₁ – объем видов деятельности растениеводства и животноводства; a_bj – норматив затрат труда на единицу деятельности за год; х₂₅ - количество привлекаемых трудовых ресурсов в целом за год, чел.-ч; В₆ – наличие трудовых ресурсов в хозяйстве;

7) по использованию трудовых ресурсов в мае а₇₁х₁ + а₇₂х₂ +…+ а₇₂₁х₂₁ ≤В₇ + х₂₆,

где а_7j – норма затрат труда в мае в расчете на единицу j-го вида деятельности; В₇ – наличие трудовых ресурсов в хозяйстве в мае; х₂₆ - привлечение трудовых ресурсов в мае.

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

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

3. По кормовым ресурсам: по производству и использованию кормов, объему покупных кормов, использованию побочной продукции, зеленому конвейеру аналогично модели структуры посевных площадей.

4. По производственным фондам и капитальным вложениям.

Эта подсистема ограничений включает обычно блок неравенств по использованию производственных помещений в животноводстве:

 

где D – число видов отраслей животноводства; х_i – число дополнительных скотомест; I₄ – множество видов производственных помещений для определения отрасли производства.

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

 

где I₁ – множество трансформируемых земельных угодий; a_ui - норматив капитальных вложений на единицу пополняемого ресурса; u – индекс капитальных вложений; I₅ – множество видов животноводческих помещений; B_u – возможный объем капитальных вложений.

5. По минеральным и органическим удобрениям.

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

 

где a_ij – доза внесения минеральных удобрений i-го вида на 1 га j-ой культуры; x_i  - переменная по общей потребности в минеральных удобрениях i-го вида; I_i``- подмножество видов минеральных удобрений.

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

 

где a_ij – доза внесения удобрений в расчете на единицу j-го вида деятельности растениеводства; v_ij – норма выхода органических удобрений в расчете на единицу j-го вида деятельности животноводства; I_s`` - подмножество органических удобрений.

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

6. По реализации продукции:

 

где v_ej – выход товарной продукции е-го вида в расчете на единицу j-го вида деятельности растениеводства или животноводства; е – индекс вида товарной продукции;

Q_e – объем реализации продукции е-го вида, прогнозируемый либо принимаемый в соответствии с заключенными договорами поставки (в соответствующих единицах измерения);

J` - подмножество видов деятельности растениеводства и животноводства, продукция которых имеет товарное назначение; Е – множество видов товарной продукции.

7. Дополнительные ограничения по размерам растениеводств и животноводства:

 

где A_j – допустимый размер j-го вида деятельности растениеводства или животноводства; J``- подмножество видов деятельности по размерам, которые вводят в соответствии с ограничениями.

8. По соотношению размеров отдельных видов деятельности.

С помощью условий пропорциональности связи обеспечивают:

а) определенное соотношение между размерами посевов отдельных культур (предшественников в севообороте)

 

где N` - подмножество культур-предшественников;

б) определенное соотношение отдельных половозрастных групп скота или птицы по структуре стада

 

где g_j` и g<sub>j</sub>`` - минимальный и максимальный пределы j-й половозрастной группы животных в структуре стада в долях; D` - подмножество половозрастных групп скота и птицы.

9. По определению денежных средств на производство и реализацию товарной продукции в денежных единицах:

 

где a_ij, a_is – коэффициенты затрат денежных средств на производство и реализацию единицы j-го вида деятельности (a_ij) и единицу покупного корма (a_is); x_i^s – переменная по общему объему затрат и денежных средств; I₉ – множество взаимосвязей по денежным средствам при вариантных расчетах.

10. По определению стоимости товарной продукции в денежных единицах:

 

где h – индекс стоимостного показателя; c_hj – выход товарной продукции в расчете на единицу j-го вида деятельности, денежных единиц; Н - множество стоимостных показателей при вариантных расчетах; x_h – переменная по объему значимого стоимостного показателя, денежных единиц.

При условии неотрицательности переменных x_j ≥ 0;  x_jk ≥ 0;  x_i ≥ 0;   x_t^s ≥ 0;   x_j ≥ 0;   x_h ≥ 0;   x_i^t ≥ 0

Задание 2

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

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

1.  

Х₁ + 2Х₂ ≥ 6

Х₁ ≥ 1, 2Х₂ ≥3

Z (х) = 5Х₁ + 10Х₂

РЕШЕНИЕ

Построение граничных прямых, соответствующих системе ограничений

Прямая l₁. По условию задачи ограничение записано как неравенство 2Х₁ + Х₂ ≥ 6, которому соответствует граничная прямая l₁: 2Х₁ + Х₂ = 6.

Найдем точки пресечения l₁с осями координат, для этого одну из переменных приравниваем к нулю и определяем значение второй переменной:

при Х₁ = 0, Х₂ = 6, тогда прямая l₁пресекает ось Ох₂ в точке А₁ (0; 6);

при Х₂ = 0, Х₁ = 3, следовательно, точка пересечения прямой l₁с осью Ох₁ имеет координаты B1 (3; 0).

Граничную прямую l₁построим по точкам А₁ (0; 6), B₁ (3; 0).

Аналогично построим граничные прямые для остальных неравенств.

Прямая l₂. Второе неравенство Х₁ + 2Х₂ ≥ 6 заменяем уравнением Х₁ + 2Х₂ ≥ 6. При Х₁ = 0, Х₂ = 3, а при Х₂ = 0, Х₁ = 6. Тогда граничная прямая l₂пересекает оси координат в точках А₂ (0; 3) и B₂ (6; 0).

Прямая l₃. Третьему неравенству Х₁ ≥ 1 соответствует граничная прямая l₃, проходящая через точку B₃ (1; 0) параллельно оси Oх₂.

Прямая l₄. Четвертое неравенству 2Х₂ ≥3 соответствует граничная прямая l₄, проходящая через точку A₃ (0; 1,5) параллельно оси Oх₁.

На координатных осях отмечаем возможные значения Х₁ и Х₂, при необходимости на осях можно выбрать различные единицы масштаба.

Определение области допустимых решений

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

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

Обозначим границы области многоугольника решений.

Построение вектора градиента и линии уровня

Построим прямую, отвечающую значению функции Z = 0:
Z = 5x₁+10x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации Z(X). Начало вектора – точка (0; 0), конец – точка (5; 10). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Область допустимых решений представляет собой многоугольник

Нахождение точки экстремума

Точка минимума.

Прямая Z(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых l₁ и l₂, то ее координаты удовлетворяют уравнениям этих прямых:

2x₁+x₂=6

x₁+2x₂=6

Решив систему уравнений, получим: x₁ = 2, x₂ = 2 Откуда найдем минимальное значение целевой функции: Z(X) = 5*2 + 10*2 = 30. Поскольку целевая функция Z(x) параллельна прямой l₂, то на отрезке BC функция Z(x) будет принимает одно и тоже минимальное значение. Для определения координат точки C решим систему двух линейных уравнений:

x₁+2x₂=6

2x₂=3

Решив систему уравнений, получим: x₁ = 3, x₂ = 1,5. Откуда найдем минимальное значение целевой функции: Z(X) = 5*3 + 10*1,5 = 30.

Точка максимума.

Задача не имеет допустимых решений. ОДР представляет собой бесконечное множество (не ограничена):

Задание 3

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

1. Решить задачу в симплексных таблицах (условие задачи переписывается).
2. Из последней симплексной таблицы записать полученное оптимальное решение, если решения нет, то обосновать причину.
3. Провести проверку полученного решения путем подстановки результата в исходную задачу.

1. Z _min = X₁ - 4X₂  - 3X₃

2X₁ + X₂ + 3X₃ <= 7

-4X₁ + 3X₂ - 2X₃ <= 9

X₁ + 2X₂ + X₃ <= 6

X_j ≥ 0, j = 1÷2

РЕШЕНИЕ

1. Решить задачу в симплексных таблицах (условие задачи переписывается).

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

Определим минимальное значение целевой функции Z(X) = x₁ - 4x₂ - 3x₃ при следующих условиях-ограничений.

2x₁ + x₂ + 3x₃≤7

- 4x₁ + 3x₂ - 2x₃≤9

x₁ + 2x₂ + x₃≤6

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₄. В 2-м неравенстве смысла (≤) вводим базисную переменную x₅. В 3-м неравенстве смысла (≤) вводим базисную переменную x₆.

2x₁ + 1x₂ + 3x₃ + 1x₄ + 0x₅ + 0x₆ = 7

-4x₁ + 3x₂-2x₃ + 0x₄ + 1x₅ + 0x₆ = 9

1x₁ + 2x₂ + 1x₃ + 0x₄ + 0x₅ + 1x₆ = 6

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

 

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

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

Решим систему уравнений относительно базисных переменных: x₄, x₅, x₆

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,7,9,6)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6
x4	7	2	1	3	1	0	0
x5	9	-4	3	-2	0	1	0
x6	6	1	2	1	0	0	1
Z(X0)	0	-1	4	3	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент .

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (7 : 1 , 9 : 3 , 6 : 2 ) = 3

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	7	2	1	3	1	0	0	7
x5	9	-4	3	-2	0	1	0	3
x6	6	1	2	1	0	0	1	3
Z(X1)	0	-1	4	3	0	0	0	0

Поскольку в последнем столбце присутствует несколько минимальных элементов 3, то номер строки выбираем по правилу Креко.

Метод Креко заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения min=3, делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₆ в план 1 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₆ плана 0 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
7-(6 • 1):2	2-(1 • 1):2	1-(2 • 1):2	3-(1 • 1):2	1-(0 • 1):2	0-(0 • 1):2	0-(1 • 1):2
9-(6 • 3):2	-4-(1 • 3):2	3-(2 • 3):2	-2-(1 • 3):2	0-(0 • 3):2	1-(0 • 3):2	0-(1 • 3):2
6 : 2	1 : 2	2 : 2	1 : 2	0 : 2	0 : 2	1 : 2
0-(6 • 4):2	-1-(1 • 4):2	4-(2 • 4):2	3-(1 • 4):2	0-(0 • 4):2	0-(0 • 4):2	0-(1 • 4):2

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x4	4	3/2	0	5/2	1	0	-1/2
x5	0	-11/2	0	-7/2	0	1	-3/2
x2	3	½	1	1/2	0	0	1/2
Z(X1)	-12	-3	0	1	0	0	-2

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент .

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее:

min (4 : 2¹/₂ , - , 3 : ¹/₂ ) = 1³/₅

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (2¹/₂) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	4	11/2	0	21/2	1	0	-1/2	13/5
x5	0	-51/2	0	-31/2	0	1	-11/2	-
x2	3	1/2	1	1/2	0	0	1/2	6
Z(X2)	-12	-3	0	1	0	0	-2	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₄ в план 2 войдет переменная x₃.

Строка, соответствующая переменной x₃ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент РЭ=2¹/₂

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₃ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₃ и столбец x₃.

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
4 : 21/2	11/2 : 21/2	0 : 21/2	21/2 : 21/2	1 : 21/2	0 : 21/2	-1/2 : 21/2
0-(4 • -31/2):21/2	-51/2-(11/2 • -31/2):21/2	0-(0 • -31/2):21/2	-31/2-(21/2 • -31/2):21/2	0-(1 • -31/2):21/2	1-(0 • -31/2):21/2	-11/2-(-1/2 • -31/2):21/2
3-(4 • 1/2):21/2	1/2-(11/2 • 1/2):21/2	1-(0 • 1/2):21/2	1/2-(21/2 • 1/2):21/2	0-(1 • 1/2):21/2	0-(0 • 1/2):21/2	1/2-(-1/2 • 1/2):21/2
-12-(4 • 1):21/2	-3-(11/2 • 1):21/2	0-(0 • 1):21/2	1-(21/2 • 1):21/2	0-(1 • 1):21/2	0-(0 • 1):21/2	-2-(-1/2 • 1):21/2

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x3	8/5	3/5	0	1	2/5	0	-1/5
x5	28/5	-17/5	0	0	7/5	1	-11/5
x2	11/5	1/5	1	0	-1/5	0	3/5
Z(X2)	-68/5	-18/5	0	0	-2/5	0	-9/5

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6
x3	8/5	3/5	0	1	2/5	0	-1/5
x5	28/5	-17/5	0	0	7/5	1	-11/5
x2	11/5	1/5	1	0	-1/5	0	3/5
Z(X3)	-68/5	-18/5	0	0	-2/5	0	-9/5

1. Из последней симплексной таблицы записать полученное оптимальное решение, если решения нет, то обосновать причину.

Оптимальный план можно записать так:

x₃ = 1³/₅

x₂ = 2¹/₅

x₁ = 0

Z(X) = -3•1³/₅ -4•2¹/₅ = -13³/₅

Анализ оптимального плана. В оптимальный план вошла дополнительная переменная x₅. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 5³/₅

Значение 3³/₅> 0 в столбце x₁ означает, что использование x₁ - не выгодно.

Значение 0 в столбце x₂ означает, что использование x₂ - выгодно.

Значение 0 в столбце x₃ означает, что использование x₃ - выгодно.

Значение ²/₅ в столбце x₄ означает, что теневая цена (двойственная оценка) равна ²/₅.

Значение 1⁴/₅ в столбце x₆ означает, что теневая цена (двойственная оценка) равна 1⁴/₅.

1. Провести проверку полученного решения путем подстановки результата в исходную задачу.

Подставляем полученное решение в систему ограничений:

x₃ = 1³/₅

x₂ = 2¹/₅

x₁ = 0

2×0 + 2¹/₅  + 3×1³/₅ =7<= 7

-4×0 + 3×2¹/₅  - 2×1³/₅=3²/₅<= 9

0 + 2×2¹/₅  + 1³/₅ 6<= 6.

Все неравенства выполняются.

Задание 4

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

1.Записать экономико-математическую модель задачи.

2.Из последней таблицы записать полученное оптимальное решение

Из трех овощеводческих хозяйства необходимо доставить в 4 магазина города картофель. Из 1 хозяйства требуется вывезти 200 т картофеля, из 2 - 100 т, из 3 - 120 т. Заявки магазинов на поставку картофеля: 1 - 60 т, 2 - 155 т, 3 - 90т,4 - 115 т.

Себестоимость перевозок задана таблицей.(1 т .руб.)

Номер хозяйства	Номер магазина
	1	2	3	4
1	110	101	95	120
2	88	91	103	96
3	76	120	85	140

Необходимо составить план перевозок картофеля от совхозов до магазинов, чтобы обеспечить минимум затрат на транспортировку всего объема картофеля.

РЕШЕНИЕ

1.Записать экономико-математическую модель задачи.

Составление экономико-математической модели задачи

Обозначим: x_ij– количество картофеля, перевозимого из i-го хозяйства (i = 1, 2, 3) в j-ый магазин (j = 1, 2, …, 4).

Экономико-математическая модель задачи в общей форме:

Найти значения переменных x_ij, которое бы обеспечивало минимальное значение целевой функции Z_min= 110х₁₁ + 101х₁₂ + 95х₁₃ + 120х₁₄ + 88х₂₁ + 91х₂₂ +103х₂₃ + 96х₂₄ + 76х₃₁ + 120х₃₂ + 85х₃₃ + 140х₃₄, при условиях неотрицательности переменных x_ij (x_ij≥ 0) и ограничениях:

Ограничения по поставщикам (тонн)
х11 + х12 + х13 + х14=200 х21 + х22 +х23 + х24 =100 х31 + х32 + х33 + х34=120   х11 +х21 + х31 =60 х12 + х22 +х32 =155 х13 +х23 +х33 =90 х14 + х24 + х34=115	– на количество картофеля в 1-ом хозяйстве, – на количество картофеля во 2-ом хозяйстве, – на количество картофеля в 3-ем хозяйстве, Ограничения по потребителям (тонн) – на количество картофеля в 1-ом магазине, – на количество картофеля во 2-ом магазине, – на количество картофеля в 3-ем магазине – на количество картофеля в 4-ем магазине

2. Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.

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

 

	1	2	3	4	Запасы
1	110	101	95	120	200
2	88	91	103	96	100
3	76	120	85	140	120
Потребности	60	155	90	115

Проверим необходимое и достаточное условие разрешимости задачи.

∑ a = 200 + 100 + 120 = 420

∑ b = 60 + 155 + 90 + 115 = 420

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	110	101	95	120	200
2	88	91	103	96	100
3	76	120	85	140	120
Потребности	60	155	90	115

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

Этап I. Поиск первого опорного плана.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен 110

Для этого элемента запасы равны 200, потребности 60. Поскольку минимальным является 60, то вычитаем его.

x₁₁ = min(200,60) = 60.

110	101	95	120	200 - 60 = 140
x	91	103	96	100
x	120	85	140	120
60 - 60 = 0	155	90	115	0

Искомый элемент равен 101

Для этого элемента запасы равны 140, потребности 155. Поскольку минимальным является 140, то вычитаем его.

x₁₂ = min(140,155) = 140.

110	101	x	x	140 - 140 = 0
x	91	103	96	100
x	120	85	140	120
0	155 - 140 = 15	90	115	0

Искомый элемент равен 91

Для этого элемента запасы равны 100, потребности 15. Поскольку минимальным является 15, то вычитаем его.

x₂₂ = min(100,15) = 15.

110	101	x	x	0
x	91	103	96	100 - 15 = 85
x	x	85	140	120
0	15 - 15 = 0	90	115	0

Искомый элемент равен 103

Для этого элемента запасы равны 85, потребности 90. Поскольку минимальным является 85, то вычитаем его.

x₂₃ = min(85,90) = 85.

110	101	x	x	0
x	91	103	x	85 - 85 = 0
x	x	85	140	120
0	0	90 - 85 = 5	115	0

Искомый элемент равен 85

Для этого элемента запасы равны 120, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x₃₃ = min(120,5) = 5.

110	101	x	x	0
x	91	103	x	0
x	x	85	140	120 - 5 = 115
0	0	5 - 5 = 0	115	0

Искомый элемент равен 140

Для этого элемента запасы равны 115, потребности 115. Поскольку минимальным является 115, то вычитаем его.

x₃₄ = min(115,115) = 115.

110	101	x	x	0
x	91	103	x	0
x	x	85	140	115 - 115 = 0
0	0	0	115 - 115 = 0	0

	1	2	3	4	Запасы
1	110[60]	101[140]	95	120	200
2	88	91[15]	103[85]	96	100
3	76	120	85[5]	140[115]	120
Потребности	60	155	90	115

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

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

Z(x) = 110*60 + 101*140 + 91*15 + 103*85 + 85*5 + 140*115  = 47385

Значение целевой функции для этого опорного плана равно:

110*60 + 101*140 + 91*15 + 103*85 + 85*5 + 140*115  = 47385

Этап II. Улучшение опорного плана.

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

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

Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Δ_ij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки х_ij=1 от поставщика А_i к потребителю В_j.

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

Величина Δ_ij называется оценкой свободной клетки (или характеристика).

В исходном решении задачи имеются клетки свободные от поставок.

Необходимо вычислить значение оценок Δ_ij для этих свободных от поставок клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.).

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

Причем одна из вершин находится в свободной от поставки клетке, в той, для которой определяется оценка Δ_ij. Все другие вершины находятся в базисных клетках, т.е. клетках, занятых поставками.

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

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

Следующий этап решения транспортной задачи заключается в улучшении опорного плана.

Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками Δ_ij, то за один переход к лучшему плану можно занять поставкой только одну клетку – ту, которая обеспечивает наибольшее снижение целевой функции.

Шаг 1. Определяем оценку для каждой свободной клетки.

(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[60]	101[140][-]	95[+]	120	200
2	88	91[15][+]	103[85][-]	96	100
3	76	120	85[5]	140[115]	120
Потребности	60	155	90	115

Цикл приведен в таблице (1,3 → 1,2 → 2,2 → 2,3).

Оценка свободной клетки равна Δ₁₃ = (95) - (101) + (91) - (103) = -18.

(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	110[60]	101[140][-]	95	120[+]	200
2	88	91[15][+]	103[85][-]	96	100
3	76	120	85[5][+]	140[115][-]	120
Потребности	60	155	90	115

Цикл приведен в таблице (1,4 → 1,2 → 2,2 → 2,3 → 3,3 → 3,4).

Оценка свободной клетки равна Δ₁₄ = (120) - (101) + (91) - (103) + (85) - (140) = -48.

(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[60][-]	101[140][+]	95	120	200
2	88[+]	91[15][-]	103[85]	96	100
3	76	120	85[5]	140[115]	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,1 → 2,2 → 1,2 → 1,1).

Оценка свободной клетки равна Δ₂₁ = (88) - (91) + (101) - (110) = -12.

(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[60]	101[140]	95	120	200
2	88	91[15]	103[85][-]	96[+]	100
3	76	120	85[5][+]	140[115][-]	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,4 → 2,3 → 3,3 → 3,4).

Оценка свободной клетки равна Δ₂₄ = (96) - (103) + (85) - (140) = -62.

(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	110[60][-]	101[140][+]	95	120	200
2	88	91[15][-]	103[85][+]	96	100
3	76[+]	120	85[5][-]	140[115]	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,1 → 3,3 → 2,3 → 2,2 → 1,2 → 1,1).

Оценка свободной клетки равна Δ₃₁ = (76) - (85) + (103) - (91) + (101) - (110) = -6.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[60]	101[140]	95	120	200
2	88	91[15][-]	103[85][+]	96	100
3	76	120[+]	85[5][-]	140[115]	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,2 → 3,3 → 2,3 → 2,2).

Оценка свободной клетки равна Δ₃₂ = (120) - (85) + (103) - (91) = 47.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (2,4;) равные: (-62).

Переход от неоптимального опорного плана к лучшему.

Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (2;4) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 85. Прибавляем 85 к объемам грузов, стоящих в плюсовых клетках и вычитаем 85 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	110[60]	101[140]	95	120	200
2	88	91[15]	103	96[85]	100
3	76	120	85[90]	140[30]	120
Потребности	60	155	90	115

110*60 + 101*140 + 91*15 + 96*85 + 85*90 + 140*30  = 42115

Шаг 2. Определяем оценку для каждой свободной клетки.

(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[60]	101[140][-]	95[+]	120	200
2	88	91[15][+]	103	96[85][-]	100
3	76	120	85[90][-]	140[30][+]	120
Потребности	60	155	90	115

Цикл приведен в таблице (1,3 → 1,2 → 2,2 → 2,4 → 3,4 → 3,3).

Оценка свободной клетки равна Δ₁₃ = (95) - (101) + (91) - (96) + (140) - (85) = 44.

(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[60]	101[140][-]	95	120[+]	200
2	88	91[15][+]	103	96[85][-]	100
3	76	120	85[90]	140[30]	120
Потребности	60	155	90	115

Цикл приведен в таблице (1,4 → 1,2 → 2,2 → 2,4).

Оценка свободной клетки равна Δ₁₄ = (120) - (101) + (91) - (96) = 14.

(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	110[60][-]	101[140][+]	95	120	200
2	88[+]	91[15][-]	103	96[85]	100
3	76	120	85[90]	140[30]	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,1 → 2,2 → 1,2 → 1,1).

Оценка свободной клетки равна Δ₂₁ = (88) - (91) + (101) - (110) = -12.

(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[60]	101[140]	95	120	200
2	88	91[15]	103[+]	96[85][-]	100
3	76	120	85[90][-]	140[30][+]	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,3 → 2,4 → 3,4 → 3,3).

Оценка свободной клетки равна Δ₂₃ = (103) - (96) + (140) - (85) = 62.

(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[60][-]	101[140][+]	95	120	200
2	88	91[15][-]	103	96[85][+]	100
3	76[+]	120	85[90]	140[30][-]	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,1 → 3,4 → 2,4 → 2,2 → 1,2 → 1,1).

Оценка свободной клетки равна Δ₃₁ = (76) - (140) + (96) - (91) + (101) - (110) = -68.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	110[60]	101[140]	95	120	200
2	88	91[15][-]	103	96[85][+]	100
3	76	120[+]	85[90]	140[30][-]	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,2 → 3,4 → 2,4 → 2,2).

Оценка свободной клетки равна Δ₃₂ = (120) - (140) + (96) - (91) = -15.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (3,1;) равные: (-68).

Переход от неоптимального опорного плана к лучшему.

Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (3;1) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	110[45]	101[155]	95	120	200
2	88	91	103	96[100]	100
3	76[15]	120	85[90]	140[15]	120
Потребности	60	155	90	115

110*45 + 101*155 + 96*100 + 76*15 + 85*90 + 140*15  = 41095

Шаг 3. Определяем оценку для каждой свободной клетки.

(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	110[45][-]	101[155]	95[+]	120	200
2	88	91	103	96[100]	100
3	76[15][+]	120	85[90][-]	140[15]	120
Потребности	60	155	90	115

Цикл приведен в таблице (1,3 → 1,1 → 3,1 → 3,3).

Оценка свободной клетки равна Δ₁₃ = (95) - (110) + (76) - (85) = -24.

(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[45][-]	101[155]	95	120[+]	200
2	88	91	103	96[100]	100
3	76[15][+]	120	85[90]	140[15][-]	120
Потребности	60	155	90	115

Цикл приведен в таблице (1,4 → 1,1 → 3,1 → 3,4).

Оценка свободной клетки равна Δ₁₄ = (120) - (110) + (76) - (140) = -54.

(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[45]	101[155]	95	120	200
2	88[+]	91	103	96[100][-]	100
3	76[15][-]	120	85[90]	140[15][+]	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,1 → 2,4 → 3,4 → 3,1).

Оценка свободной клетки равна Δ₂₁ = (88) - (96) + (140) - (76) = 56.

(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[45][+]	101[155][-]	95	120	200
2	88	91[+]	103	96[100][-]	100
3	76[15][-]	120	85[90]	140[15][+]	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,2 → 2,4 → 3,4 → 3,1 → 1,1 → 1,2).

Оценка свободной клетки равна Δ₂₂ = (91) - (96) + (140) - (76) + (110) - (101) = 68.

(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[45]	101[155]	95	120	200
2	88	91	103[+]	96[100][-]	100
3	76[15]	120	85[90][-]	140[15][+]	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,3 → 2,4 → 3,4 → 3,3).

Оценка свободной клетки равна Δ₂₃ = (103) - (96) + (140) - (85) = 62.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[45][+]	101[155][-]	95	120	200
2	88	91	103	96[100]	100
3	76[15][-]	120[+]	85[90]	140[15]	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,2 → 3,1 → 1,1 → 1,2).

Оценка свободной клетки равна Δ₃₂ = (120) - (76) + (110) - (101) = 53.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (1,4;) равные: (-54).

Переход от неоптимального опорного плана к лучшему.

Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (1;4) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	110[30]	101[155]	95	120[15]	200
2	88	91	103	96[100]	100
3	76[30]	120	85[90]	140	120
Потребности	60	155	90	115

110*30 + 101*155 + 120*15 + 96*100 + 76*30 + 85*90  = 40285

Шаг 4. Определяем оценку для каждой свободной клетки.

(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[30][-]	101[155]	95[+]	120[15]	200
2	88	91	103	96[100]	100
3	76[30][+]	120	85[90][-]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (1,3 → 1,1 → 3,1 → 3,3).

Оценка свободной клетки равна Δ₁₃ = (95) - (110) + (76) - (85) = -24.

(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	110[30][-]	101[155]	95	120[15][+]	200
2	88[+]	91	103	96[100][-]	100
3	76[30]	120	85[90]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,1 → 2,4 → 1,4 → 1,1).

Оценка свободной клетки равна Δ₂₁ = (88) - (96) + (120) - (110) = 2.

(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[30]	101[155][-]	95	120[15][+]	200
2	88	91[+]	103	96[100][-]	100
3	76[30]	120	85[90]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,2 → 2,4 → 1,4 → 1,2).

Оценка свободной клетки равна Δ₂₂ = (91) - (96) + (120) - (101) = 14.

(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[30][-]	101[155]	95	120[15][+]	200
2	88	91	103[+]	96[100][-]	100
3	76[30][+]	120	85[90][-]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,3 → 2,4 → 1,4 → 1,1 → 3,1 → 3,3).

Оценка свободной клетки равна Δ₂₃ = (103) - (96) + (120) - (110) + (76) - (85) = 8.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	110[30][+]	101[155][-]	95	120[15]	200
2	88	91	103	96[100]	100
3	76[30][-]	120[+]	85[90]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,2 → 3,1 → 1,1 → 1,2).

Оценка свободной клетки равна Δ₃₂ = (120) - (76) + (110) - (101) = 53.

(3;4): В свободную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[30][+]	101[155]	95	120[15][-]	200
2	88	91	103	96[100]	100
3	76[30][-]	120	85[90]	140[+]	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,4 → 3,1 → 1,1 → 1,4).

Оценка свободной клетки равна Δ₃₄ = (140) - (76) + (110) - (120) = 54.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (1,3;) равные: (-24).

Переход от неоптимального опорного плана к лучшему.

Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (1;3) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

	1	2	3	4	Запасы
1	110	101[155]	95[30]	120[15]	200
2	88	91	103	96[100]	100
3	76[60]	120	85[60]	140	120
Потребности	60	155	90	115

101*155 + 95*30 + 120*15 + 96*100 + 76*60 + 85*60  = 39565

Шаг 5. Определяем оценку для каждой свободной клетки.

(1;1): В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110[+]	101[155]	95[30][-]	120[15]	200
2	88	91	103	96[100]	100
3	76[60][-]	120	85[60][+]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (1,1 → 1,3 → 3,3 → 3,1).

Оценка свободной клетки равна Δ₁₁ = (110) - (95) + (85) - (76) = 24.

(2;1): В свободную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110	101[155]	95[30][-]	120[15][+]	200
2	88[+]	91	103	96[100][-]	100
3	76[60][-]	120	85[60][+]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,1 → 2,4 → 1,4 → 1,3 → 3,3 → 3,1).

Оценка свободной клетки равна Δ₂₁ = (88) - (96) + (120) - (95) + (85) - (76) = 26.

(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	110	101[155][-]	95[30]	120[15][+]	200
2	88	91[+]	103	96[100][-]	100
3	76[60]	120	85[60]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,2 → 2,4 → 1,4 → 1,2).

Оценка свободной клетки равна Δ₂₂ = (91) - (96) + (120) - (101) = 14.

(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110	101[155]	95[30][-]	120[15][+]	200
2	88	91	103[+]	96[100][-]	100
3	76[60]	120	85[60]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (2,3 → 2,4 → 1,4 → 1,3).

Оценка свободной клетки равна Δ₂₃ = (103) - (96) + (120) - (95) = 32.

(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110	101[155][-]	95[30][+]	120[15]	200
2	88	91	103	96[100]	100
3	76[60]	120[+]	85[60][-]	140	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,2 → 3,3 → 1,3 → 1,2).

Оценка свободной клетки равна Δ₃₂ = (120) - (85) + (95) - (101) = 29.

(3;4): В свободную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	110	101[155]	95[30][+]	120[15][-]	200
2	88	91	103	96[100]	100
3	76[60]	120	85[60][-]	140[+]	120
Потребности	60	155	90	115

Цикл приведен в таблице (3,4 → 3,3 → 1,3 → 1,4).

Оценка свободной клетки равна Δ₃₄ = (140) - (85) + (95) - (120) = 30.

Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Zx невозможно, поскольку она достигла минимального значения.

Таким образом, последний опорный план является оптимальным.

Минимальные затраты составят:

101*155 + 95*30 + 120*15 + 96*100 + 76*60 + 85*60  = 39565

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

Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп—(m+n—1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 — 361 цикл.

Анализ оптимального плана.

Из 1-го хозяйства необходимо груз направить в 2-й магазин (155), в 3-й магазин (30), в 4-й магазин (15)

Из 2-го хозяйства необходимо весь груз направить в 4-й магазин

Из 3-го хозяйства необходимо груз направить в 1-й магазин (60), в 3-й магазин (60)

Список литературы

1. Математическое моделирование в менеджменте. Уч. пос. под ред. Трояновского В.М. М: Русская Деловая Литература, 2009. - 240 с.

2. Курносов А.П. Вычислительная техника и программирование. - М., Финансы и статистика, 2011-334с.

3. Карасев А.И., Кремер Н.Ш., Савельева Т.И. Математические методы и модели в планировании. -М. ,2010

4. Лопатников Л.И. Экономико-математический словарь.-М.,2011.

5. Баусов Л.И. Нелинейное программирование. М.: ФА, 2010.

---

Понравилось? Нажмите на кнопочку ниже. Вам не сложно, а нам приятно).

---

Чтобы скачать бесплатно Контрольные работы на максимальной скорости, зарегистрируйтесь или авторизуйтесь на сайте.

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

---

Друзья! У вас есть уникальная возможность помочь таким же студентам как и вы! Если наш сайт помог вам найти нужную работу, то вы, безусловно, понимаете как добавленная вами работа может облегчить труд другим.

Добавить работу

---

Если Контрольная работа, по Вашему мнению, плохого качества, или эту работу Вы уже встречали, сообщите об этом нам.

---

Добавление отзыва к работе

Добавить отзыв могут только зарегистрированные пользователи.

---