Кафедра автоматизации производственных процессов

Кафедра автоматизации производственных процессов

Лапшина М.Л.

Учебное пособие по дисциплине

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

 

 

Воронеж 2019

Содержание

ВВЕДЕНИЕ		3
1.	МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ ОПТИМИЗАЦИИ	3
2	ОПТИМИЗАЦИОННАЯ МОДЕЛЬ	6
3	КЛАССИФИКАЦИЯ ЗАДАЧ И МЕТОДОВ ОПТИМИЗАЦИИ	8
4	ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ	10
	4.1 Основные определения	10
	4.2 Пример решения задачи линейного программирования	11
5	Симплексный метод решения задачи линейного программирования	13
	5.1. Пример решения задачи симплексным методом	13
	5.2. Метод искусственного базиса	17
6	ВЗАИМНО ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ	18
7	ТРАНСПОРТНАЯ ЗАДАЧА	20
	7.1. Пример транспортной задачи	22
8	МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА	25
	8.1. Пример решения задачи	25
9	ЗАДАЧА ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ	27
	9.1 Пример решения задачи	27
10	ОБЩИЕ ПОНЯТИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ	28
	10.1. Пример решения задачи	29
11.	СЕТЕВАЯ МОДЕЛЬ	32
	11.1. Пример решения задачи	33
12	МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ	37
	12.1 Причины появления многокритериальности	37
	12.2 Примеры сверток	39
	12.3 Теорема о свертке	42
	12.4 Примеры	44
13	ОПТИМАЛЬНОСТЬ ПО ПАРЕТО	45
14	ПОИСК ЭФФЕКТИВНЫХ ТОЧЕК	47
	14.1 Примеры	50
15	ЗАДАЧИ	51
16	МЕТОД ГОМОРИ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ	54
	16.1 Метод ветвей и границ решения задач целочисленного программирования	58
17	НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ	64
СПИСОК ЛИТЕРАТУРЫ		68

ВВЕДЕНИЕ

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

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

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

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

· построение экономических и математических моделей для задач принятия решений в сложных ситуациях или в условии неопределенности;

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

ОПТИМИЗАЦИОННАЯ МОДЕЛЬ

Оптимальная (или оптимизационная) модель [optimization model] - экономико-математическая модель, которая охватывает некоторое число вариантов (технологических способов) производства, распределения или потребления и предназначена для выбора таких значений переменных, характеризующих эти варианты, чтобы был найден лучший из них.

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

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

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

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

1. принцип достаточности используемой информации;

2. принцип инвариантности используемой информации;

3. принцип преемственности модели;

4. принцип эффективной реализуемости комплекса экономико-математических моделей.

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

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

1. определение границ объекта оптимизации;

2. выбор управляемых переменных;

3. определение ограничений на управляемые переменные;

4. выбор критерия оптимизации;

5. формулировка математической задачи

Оптимальная (или оптимизационная) задача [optimization problem] - экономико-математическая задача, цель которой состоит в нахождении наилучшего (с точки зрения какого-то критерия) распределения наличных ресурсов, иногда то же, экстремальная задача решается с помощью оптимальной модели методами математического программирования, т. е. путем поиска максимума или минимума некоторых функций или функционалов при заданных ограничениях (условная оптимизация) и без ограничений (безусловная оптимизация).

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

 

Пример решения задачи линейного программирования

Задача 1. (об использовании ресурсов).

Для изготовления двух видов продукции р₁ и р₂ используют четыре вида ресурсов s₁, s₂, s₃, s₄. запасы ресурсов, затрачиваемых на производство единицы продукции, приведены в таблице 1.

Таблица 1

Вид ресурса	№запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		р1	р2
s1	18	1	3
s2	16	2	1
s3	5	-	1
s4	21	3	-

 

Прибыль, получаемая от единицы продукции р₁ и р₂ – соответственно 2 и 3 руб. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Геометрический метод решения. Составим экономико-математическую модель задачи. Обозначим  - число единиц продукции соответственно  и , запланированных к производству. Для их изготовления потребуется  единиц ресурса ,  единиц ресурса s₂,  единиц ресурса  и  единиц ресурса . Так как потребление ресурсов s₁, s₂, s₃, s₄ не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

 

,

,                                                                                                  (4)

,

.

по смыслу задачи переменные

х₁³0, х₂³0                                                                                        (5)

суммарная прибыль f составит  руб. от реализации продукции  и  руб. - от реализации продукции р₂, т.е.

                                                                                     (6)

итак, экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (4) и условию (5), при котором функция (6) принимает максимальное значение:

при ограничениях:

(i)

(ii)

     (iii)

(iv)

  (v,vi)                                                                                     

Изобразим многоугольник решений на рис. 1

Рис. 1.

Очевидно, что при  линия уровня  проходит через начало координат (строить ее не обязательно). Зададим, например,  и построим линию уровня . Ее расположение указывает на направление возрастания линейной функции (вектор ). Так как рассматриваемая задача - на отыскание максимума, то оптимальное решение - в угловой точке с, находящейся на пересечении прямых i и ii, т.е. координаты точки с определяются решением системы уравнений

 

откуда , т.е. С (6;4).

Максимум (максимальное значение) линейной функции равен .

Итак,  при оптимальном решении , т.е. максимальная прибыль в 24 руб. может быть достигнyта при производстве 6 единиц продукции р₁ и 4 единиц продукции р₂.

 

Пример решения задачи симплексным методом

Задача 1 (п.4.2).

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком “плюс”, так как все неравенства имеют вид «≤».

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

,

,

,

.

Для нахождения первоначального базисного решения разобьем переменные на две группы - основные и неосновные. так как определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅,х₆, отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи. При выборе основных переменных на первом шаге не обязательно составлять определитель из их коэффициентов и проверять, равен ли он нулю. Достаточно воспользоваться следующим правилом: в качестве основных переменных на первом шаге следует выбрать (если возможно) такие m переменных, каждая из которых входит только в одно из m уравнений системы ограничений, при этом нет таких уравнений системы, в которые не ходит ни одна из этих переменных.

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

i шаг. Основные переменные: х₃, х₄, х₅, х₆. неосновные переменные: х₁, х₂. Выразим основные переменные через неосновные:

 ,                                                (7)

Положив неосновные переменные равными нулю, т.е. х₁ =0, х₂ = 0, получим базисное решение х₁= (0; 0; 18; 16; 5; 21), которое является допустимым и соответствует вершине О (0;0) многогранника ОАВСDЕ на рис. 2.

 

Рис. 2

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

При решении х₁ значение функции равно . Легко понять, что функцию f можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение для f с положительным коэффициентом. Это можно осуществить, перейдя к такому новому допустимому базисному решению, в котором эта переменная будет неосновной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). При таком переходе одна из основных переменных перейдет в неосновные, а геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функций “лучше” (по крайней мере “не хуже”). В данном примере для увеличения f можно переводить в основные либо х₁, либо х₂, так как обе эти переменные входят в выражение дня f со знаком “плюс”. Для определенности в такой ситуации будем выбирать переменную, имеющую больший коэффициент, т.е. в данном случае х₂ (такое правило выбора не всегда дает наименее трудоемкое решение, иногда имеет смысл провести предварительные специальные оценки).

Система (1) накладывает ограничения на рост переменной х₂. поскольку необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х₁ = 0 как неосновная переменная):

откуда  

Каждое уравнение системы (1), кроме последнего, определяет оценочное отношение - границу роста переменной х₂, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при х₂ при условии, что эти числа имеют разные знаки. Последнее уравнение системы не ограничивает рост переменной х₂, так как данная переменная в него не входит (или формально входит с нулевым коэффициентом). В этом случае условимся обозначать границу символом ∞. Такой же символ будем использовать, когда свободный член и коэффициент при переменной в уравнении имеют одинаковые знаки, так как и в этом случае нет ограничений на рост переменной.

Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член отсутствует (т.е. равен 0), а переводимая переменная имеет положительный коэффициент. И в этом случае граница обозначается символом ∞. Обратите внимание, что при нулевом свободном члене и отрицательном коэффициенте при переводимой переменной уравнение ограничивает рост этой переменной нулем! (любое положительное ее значение вносит отрицательную компоненту в следующее базисное решение). Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ =min (18/3; 16/1; 5/1; ∞} =5. при х₂ =5 переменная х₅ обращается в нуль и переходит в неосновные.

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

ii шаг. Основные переменные: х₂, х₃,х₄, х₆. неосновные переменные: х₁, х₅.

Выразим новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для х₂):

 

или

                                                                                   (8)

Второе базисное решение  является допустимым и соответствует вершине а (0;5) на рис. 2. Геометрическая интерпретация перехода от х₁ к х₂ — переход от вершины о к соседней вершине а на многоугольнике решений ОАBCDЕ.

Выразив линейную функцию через неосновные переменные на этом шаге, получаем:

 

Значение линейной функции f₂ = f (х₂) =15. изменение значения линейной функции легко определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в выражении для линейной функции; в данном случае    

Однако значение f₂ не является максимальным, так как повторяя рассуждения 1 шага, обнаруживаем возможность дальнейшего увеличения линейной функции за счет переменной х₁, входящей в выражение для f с положительным коэффициентом. Система уравнений (8) определяет наибольшее возможное значение для х₁: х₁ = min{∞;3/1;11/2; ∞} = 3. второе уравнение является разрешающим, переменная х₃ переходит в неосновные, при этом  

iii шаг. Основные переменные: х₁, х₂, х₄, х₆. неосновные переменные х₃, х₅.

Как и на ii шаге, выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для х_i). после преобразований получаем:

,

,

,                                                                                (9)

.

Базисное решение х₃ = (3; 5; 0; 5; 0; 12) соответствует вершине в (3;5). выражаем линейную функцию через неосновные переменные . Проверяем:  Третье допустимое базисное решение тоже не является оптимальным, поскольку при неосновной переменной х₅ в выражении линейной функции через неосновные переменные содержится положительный коэффициент. Переводим х₅ в основную переменную. при определении наибольшего возможного значения для х₅ следует обратить внимание на первое уравнение в системе (9), которое не дает ограничений на рост х₅, так как свободный член и коэффициент при х₅ имеют одинаковые знаки. Поэтому . Третье уравнение является разрешающим, и переменная х₄ переходит в неосновные; .

iv шаг. Основные переменные: х₁, х₂, х₅, х₆. неосновные переменные: х₃, х₄.

После преобразований получим:

,

,

,

.

Базисное решение  соответствует вершине с (6; 4) на рис. 2.

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

Прибыль предприятия принимает максимальное значение 24 руб. при реализации 6 единиц продукции  и 4 единиц продукции  Дополнительные переменные х₃, х₄, х₅, х₆ показывают разницу между запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов. При оптимальном плане производства , т.е. остатки ресурсов s₁ и s₂ равны нулю, а остатки, ресурсов s₃ и s₄ равны соответственно 1 и 3 единицам.

Метод искусственного базиса

Суть метода: в каждое уравнение, дающее отрицательную компоненту в базисном решении, вводим свою новую неотрицательную искусственную переменную у₁,у₂,…, у_k, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения. Составляем новую линейную функцию  где м - произвольно большое число, и ищем ее максимум (т-задача). Назовём м-функцией выражение . Справедлива теорема:

1. Если в оптимальном решении т-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е.  т.е. минимум м-функции равен 0).

2. Если имеется оптимальное решение т-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна.

3. Если Т_max= ∞, то исходная задача также неразрешима, причем либо f_max=∞, либо условия задачи противоречивы.

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

Пример двойственной задачи

Составить задачу, двойственную следующей задаче:

при ограничениях:

,

,

,

,

 

Решение. Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду «≤», для чего обе части первого и четвертого неравенства умножим на (-1), получим:

,

,

,

2. Составим расширенную матрицу системы:

а₁=

      
3. Найдем матрицу  транспонированную к а₁:

а₁¢=

4. Сформулируем двойственную задачу:

при ограничениях

,

,

  

ТРАНСПОРТНАЯ ЗАДАЧА

Особенности экономико-математической модели транспортной задачи:

• система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);

• коэффициенты при переменных системы ограничений равны единице или нулю;

• каждая переменная входит в систему ограничений два раза.

Для математической формулировки транспортной задачи в общей постановке обозначим через c _ij коэффициенты затрат, через м_i - мощности поставщиков, через n_j - мощности потребителей, где   m - число поставщиков, n - число потребителей. Тогда система ограничений примет вид:

                                                      (16)

                                                      (17)

Система (16) включает в себя уравнение баланса по строкам, а система (17) - по столбцам таблицы поставок. Линейная функция в данном случае

.                                                (18)

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

Произвольное допустимое решение  системы ограничений (16), (17) назовем распределением поставок. Такое решение задает заполнение таблицы поставок, поэтому в дальнейшем значение произвольной переменной х _ij и содержимое соответствующей клетки таблицы поставок будут отождествляться.

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

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

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

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

 

Пример транспортной задачи

Построить экономико-математическую модель следующей задачи. имеются три поставщика и четыре потребителя. мощность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары “поставщик - потребитель” сведены в таблицу поставок (табл. 3).

Таблица 3

поставщики	мощность поставщиков	потребители и их спрос
		1	2	3	4
		20	110	40	110
1	60	1 х11	2 х12	5 х13	3 х14
2	120	1 х21	6 х22	5 х23	2 х24
3	106	6 х31	3 х32	7 х33	4 х34

 

В левом верхнем углу произвольной (ij -клетки (i - номер строки, j - номер столбца) стоит так называемый коэффициент затрат - затраты на перевозку единицы груза от i-го поставщика к j -му потребителю, например, в левом верхнем углу клетки (1, 4) стоит число 3, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 3 условных денежных единицы и т. д.

Задача ставится следующим образом: найти объемы перевозок для каждой пары «поставщик — потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

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

Решение. Построим экономико-математическую модель данной задачи, искомый объем перевозки от i-го поставщика к j -му потребителю обозначим черёз x_ij и назовём поставкой клетки (i,j). Например, х₁₂ - искомый объем перевозки от 1- го поставщика ко 2-му потребителю или поставка клетки (1,2) и т. д. заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных х. так, например, объем груза, забираемого от 1 -го поставщика, должен быть равен мощности этого поставщика - 60 единицам, т.е.  (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок, т. е.

,

,                                                                 (19)

.  

 

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

,

,                                                                             (20)

,

.     

 

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует дополнительно предположить, что

 

Суммарные затраты р на перевозку выражаются через коэффициенты затрат и поставки следующим образом;

                   (21)

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

Решение. дадим переменной х₁₁ максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1,1) - “северо-западный” угол таблицы поставок: х₁₁= min {60, 20) = 20. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения (заполненные клетки будем перечеркивать сплошной линией (табл. 4) клетки, выпавшие из последующего рассмотрения, перечеркнуты пунктирной линией. в таблице поставок найдем новый “северо-западный” угол - клетку (1,2) и дадим в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 20 единиц груза и у него осталось только 40 = 60 - 20 единиц груза, получаем, что . После этого мощность 1-го поставщика полностью реализована и из рассмотрения выпадет первая строка таблицы поставок (перечеркиваем сплошной линией клетку (1,2) и пунктирной линией оставшиеся свободные клетки первой строки). в оставшейся таблице снова находим “северо-западный угол” и т. д. в результате получаем следующее исходное распределение поставок (табл.4).

Таблица 4.

	20	110	40	110
60	1 20	2 40	5	5
120	1	6 70	5 40	2 10
100	6	3	7	4 100

Решение методом наименьших затрат.

Решение. Находим в таблице поставок (табл.4) клетки с наименьшим коэффициентом затрат. Таких клеток две – (1,1) и (2,1) с коэффициентами затрат, равными 1. сравним максимально возможные поставки для этих клеток: для клетки (1,1) , для клетки (2,1) .