Составим математическую модель задачи.

Пусть –I поставщиком, А-му потребителю, тогда , – количество единиц продукта перевозимого этим же поставщиком Б-му и В-му потребителю соответственно.

Целевая функция в этом случае имеет вид:

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

2 Решение задачи в программе "Поиск решения"

Вид электронной таблицы Excel, созданной для решения задачи, в режиме отображения формул, представлен на рис. 1. Искомые значения находятся в блоке ячеек B4:D6. Адрес данного блока входит в поле вводаИзменяя ячейки в окне “Поиск решения”. Требования к ограничениям по спросу и запасам представлены соответственно в ячейках B7:D7 и E4:E6. Коэффициенты ЦФ, означающие затраты на доставку расположены в блоке ячеек B12:D14.

Формулы целевой функции и ограничений находятся соответственно в ячейке F8 и ячейках B8:D8 (ограничения по спросу), F4:F6 (ограничения по запасам).

Рис.1

Результаты поиска решения представлены на рис. 2. Значение ЦФ=1060.

Рис. 2

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

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

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

Требуется распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000 и 500 единиц груза.

Тип самолета	Число самолетов	Месячный объем перевозок одним самолетом по авиалиниям
		I		II		III		IV
1	50	15		10		20		50
2	20	30		25		10		17
3	30	25		50		30		45
Тип самолета	Эксплуатационные расходы
	I		II		III		IV
1	15		20		25		40
2	70		28		15		45
3	40		70		40		65

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

Ограничения имеют вид:

Рис. 3

Вид электронной таблицы Excel, созданной для решения задачи, в режиме отображения формул, представлен на рис. 3. Значения переменных располагаются в блоке ячеек B21:E23. Коэффициенты целевой функции, отражающие расходы на перевозку находятся по адресам B37:E39. Данные о месячных объемах перевозок одним самолетом имеются в блоке B29:E31. Задан план перевозок и число самолетов – соответственно блоки B24:E24 и F21:F21. Формулы целевой функции и ограничений находятся соответственно в ячейке F25 и ячейках B25:E25 (ограничения по плану), F21:F23 (ограничения по количеству самолетов). Результаты поиска решения приведены на рис. 4.

Рис.4

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

Механизмы	Работы
	Р1	Р2	Р3
М1	1	2	3
М2	2	4	1
М3	3	1	5

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

Целевая функция имеет вид:

Ограничения имеют вид:

Вид электронной таблицы Excel, созданной для решения задачи, в режиме отображения формул, представлен на рис. 5. Значения переменных x_ij располагаются в блоке ячеек B45:D47. Коэффициенты целевой функции, отражающие производительность механизмов, находятся по адресам B53:D55. Формулы целевой функции и ограничений находятся соответственно в ячейке E49 и ячейках E45:E47 (каждый механизм может быть назначен только на одну работу), B49:D49 (каждая работа выполняется только на одном механизме)

Рис. 5

Результаты поиска решения приведены на рис. 6. Значение ЦФ=10

Рис. 6

Примечание. Данная задача является задачей линейного булева программирования и в ней переменные x_ij должны принимать значения либо 0 либо 1. В поиске решения такое ограничение задается тремя ограничениями, по которым изменяемые ячейки в блоке (x_ij) одновременно больше либо равны 0, меньше либо равны 1 и являются целыми.

Задание

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

Вариант 1. В машину необходимо поместить четыре вида предметов, причем могут потребоваться несколько одинаковых предметов. Имеется три вида ограничений такого типа, как вес, объем и т.д. В приведенной ниже таблице даны – i-я характеристика предмета j-го наименования, c_j- полезность одного предмета j-го наименования. Требуется загрузить машину так, чтобы суммарная полезность груза была максимальной.

Ограничения	Предмет1	Предмет2	Предмет3	Предмет4	Значения ограничений
I	3	3	5	2	1000
II	4	2	4	4	600
III	3	5	4	3	600
Полезность	3	4	3	3

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

Ограничения имеют вид:

Ответ: Значение ЦФ=556.

Значения переменных x_ij располагаются в блоке ячеек B4:E4. Коэффициенты целевой функции, отражающие полезности предметов находятся по адресам B7:E7. Данные о характеристиках предметов имеются в блоке B10:E12. Заданы значения ограничений- соответственно блок H10:H12. Формулы целевой функции и ограничений находятся соответственно в ячейке F7 и ячейках F10:E12 (ограничения по свойствам).

Вариант 2. Фирма обслуживает 5 клиентов. Каждый день она доставляет своим клиентам товары на грузовых машинах. Существует 3 допустимых маршрута доставки, каждый из которых позволяет обслужить определенное количество клиентов и требует использования в течении дня одного транспортного средства. Каждый маршрут характеризуется определенными расходами (см. табл.). Необходимо выбрать такое множество маршрутов, при котором обеспечивается обслуживание каждого из клиентов и, кроме того, суммарные расходы минимальны, при условии, что каждый клиент обслуживается один раз в день.

Таблица обслуживания клиентов по маршрутам
Клиенты	Маршруты
	1	2	3
1	1		1
2	1
3	1		1
4		1
5		1	1
Расходы по маршруту	900	1000	800

Целевая функция имеет вид:

Ограничения имеют вид:

Также задаются ограничения x_ij <=1, и по целочисленности.

Ответ: Значение ЦФ=610

Вариант 3. Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140 и 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

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

Вариант 4. Для строительства трех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может изготовлять 100, 150 и 50 ус. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов соответственно равны 75, 80, 60 и 85 усл. ед. Известны также тарифы перевозок 1 усл. ед. кирпича с каждого завода к каждому из строящихся объектов.

Составить такой план перевозок кирпича, при котором общая стоимость перевозок является минимальной.

Вариант 5. Дано распределения самолетов трех типов по четырем маршрутам. Характеристики парка самолетов и движения по авиалиниям приведены в таблице.

Тип самолета	Число пассажиров	Количество cамолетов		Количество рейсов в сутки на каждом маршруте
				1		2		3		4
1	50	5		3		2		2		1
2	30	8		4		3		3		2
3	30	10		5		5		4		2
Суточный пассажиропоток				100		200		90		120
Тип самолета			Эксплуатационные расходы на 1 рейс по данному маршруту, $
			1		2		3		4
1			1000		1100		1200		1500
2			800		900		100		1000
3			600		800		800		900
Убыток от неудовлетворенного спроса (на одного неперевезенного пассажира)			40		50		45		70

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

Вариант 6. Авиакомпания «Аэрофлот» (Москва) располагает парком в 70 самолетов восьми типов.

Тип самолета	Загрузка пассажирами		Время полета без посадки, ч	Парк самолетов, шт.
	минимальная	максимальная
1. ТУ-134	68	76	7	25
2. ТУ-154	132	158	4	10
3. ИЛ-62	132	162	12	10
4. ИЛ-86	316	350	5	12
5. ИЛ-96	235	—	10	4
6. В-737	137	—	12	3
7. В-777	231	—	22	2
8.А-310	179	191	12	4

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

Рейс	Протяженность линий, ч (т)	Количество промежуточных посадок	Объем пассажирских перевозок, чел.
I. Египет - Хургада	5,5	0	4000
II. Испания - Малага	4,5	0	3500
III. Япония - Токио	11	2	35000
IV. Франция - Париж	3,5	1	7000
V. США - Нью-Йорк	9	2	6000

Вариант 7. Сельскохозяйственный кооператив «Ласточка» в области имеет три филиала Ф1, Ф2 и Ф3, которые обеспечивают поставками подсолнечных семян в соответствии с заявками пять заводов производителей подсолнечного масла А, В, С, D и Е. Объемы запасов семян, объемы заказов на поставку и тарифы на перевозку приведены в транспортной таблице.

Филиалы	Заводы					Запасы,т
	А	В	С	D	Е
Ф1	7	9	15	4	18	630
Ф2	13	12	8	15	5	710
Ф3	5	14	6	20	12	820
Заявки,тонн	400	520	480	560	540

Постройте оптимальный план перевозки подсолнечных семян с минимальными транспортными расходами

Вариант 8. Фирма «Союз» обеспечивает доставку видео- и аудиокассет с четырех складов, расположенных в разных точках города в четыре магазина. Запас кассет, имеющихся на складах, а также объемы заказов магазинов и тарифы на доставку представлены в транспортной таблице.

Склады	Магазины				Запасы, тыс. шт.
	№ 1	№2	№3	№4
Склад № 1	2	6	4	3	120
Склад №2	5	1	9	2	240
Склад № 3	3	2	2	6	80
Склад № 4	4	5	10	3	60
Заказы, шт.	190	170	110	30

Определите объемы перевозок, обеспечивающих их минимальные затраты.

Вариант 9. Московский филиал фирмы «The Coca-Cola Company», выпускающей газированные напитки приблизительно равного спроса (Sprite, Coca-Cola, Fanta), складируемые в разных местах, должен поставить свою продукцию в четыре крупных московских супермаркета: «Рамстор-1», «Рамстор-2». «Седьмой Континент», супермаркет «Арбатский».

Каждая упаковка содержит 12 банок емкостью 0,33 литра. Тарифы на доставку товара, объемы запасов и заказы на продукцию приведены в таблице.

Склады	Супермаркеты				Запасы
	«Рамстор-1»	«Рамстор-2»	«Седьмой Континент»	«Арбатский»
Coca-Cola	6	4	9	5	400
Sprite	5	7	8	6	300
Fanta	9	4	6	7	200
Заказы, уп.	150	250	150	350

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

Вариант 10. Автотранспортная компания «Астрада» обеспечивает доставку шин «Bridgestone» с трех оптовых складов, расположенных в Москве, Нижнем Новгороде и Покрове в пять магазинов в Чебоксарах, Нижнем Новгороде, Вязниках, Набережных челнах и Казани. Объемы запасов шин на складах, объемы заявок магазинов и тарифы на перевозку приведены в транспортной таблице.

Склады в городах	Магазины					Запасы
	Чебоксары	Нижний Новгород	Вязники	Набережные Челны	Казань
Москва	14	8	6	20	16	350
Нижний Новгород	6	1	2	12	8	400
Покров	12	6	4	18	14	400
Заявки	200	280	240	220	210

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

Вариант 11. Фирма «Московия» заключила контракт с компанией АЛРОСА (Алмазы России — Саха) на покупку промышленного золота для его реализации в пяти городах в объемах: Самара — 80 кг, Москва — 260 кг, Ростов-на-Дону — 100 кг, Санкт-Петербург — 140 кг. Нижний Новгород — 120 кг.

Компания располагает тремя месторождениями «Мирное», «Удачный» и «Полевое», которые планируют за год выработать соответственно 200, 250 и 250 кг золота.

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

7 9 15 4 18

С = 13 25 8 15 5

5 11 6 20 12

Вариант 12. Составьте оптимальный план перевозки автомобилей из городов Ижевск, Казань, Тольятти в города Москва, Саранск и Ульяновск. Стоимость перевозки одного автомобиля составляет 10 руб. за км. Расстояние между городами, объемы заявок и заказов представлены в таблице.

Города	Города			Запасы, шт.
	Москва	Саранск	Ульяновск
Ижевск	10500	6000	4500	20
Казань	7500	3900	2100	65
Тольятти	9000	3600	1500	80
Заказы, шт.	100	50	15

Составьте оптимальный план перевозок, обеспечивающий минимальные затраты на перевозку.

Вариант 13. Составьте оптимальный план перевозки лекарств с минимальными затратами из аптечных складов в пять аптек города: больница №15, городские клинические больницы № 7, № 23 и № 50 и институт им. Бурденко. Запасы лекарств на складах, заявки потребителей и тарифы перевозок представлены в таблице.

Склады	Аптеки больниц					Запасы
	№15	№7	№23	№50	Бурденко
АС№1	10	11	6	7	8	100
Фарма К.	10	11	8	9	12	150
ПРОТЕК	12	12	10	12	14	200
Заказы	50	200	60	100	40

Вариант 14. Составьте оптимальный план перевозки угля с минимальными транспортными расходами с шахт Варгашорская (В). Западная (3) и Комсомольская (К), еженедельно добывающих соответственно 26, 32 и 17 тыс. т. Покупатели угля расположены в разных городах А, В, С и D, заявки которых составляют 28,19,12 и 16 тыс. т соответственно. Тарифы определяет стоимость перевозки 1 тыс. т между поставщиками и потребителями представлены транспортной таблице.

Шахты	Потребители				Добыча угля, тыс. тонн в неделю
	А	В	С	D
Западная	70	76	72	68	32
Варгашорская	80	84	82	77	26
Комсомольская	80	83	82	76	17
Заявки, тыс. тонн	28	19	12	16

Вариант 15. Составьте оптимальный план завоза хлебобулочной продукции с минимальными транспортными расходами из трех пекарен фирмы «Колос» в четыре булочных города: А, В, С, D. Заказы на поставку хлебобулочных изделий, производительность пекарен и транспортные тарифы представлены в транспортной таблице.

Мини-пекарни	Булочные				Производительность пекарей, кг/сутки
	А	В	С	D
№1	4	7	6	10	830
№2	9	6	7	5	670
№3	6	7	5	8	770
Заказы, кг/сутки	520	610	380	760

 

15. Методы заполнения опорного плана транспортной задачи.

 

Метод северо-западного угла

Пусть условия транспортной задачи заданы таблице 2.3. Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя B1 за счет запаса поставщика А₁. Для этого сравниваемa₁ = 100 с b_i = 200, a₁< b₁меньший из объемов, т. е. = 100 ед. записываем в левый нижний угол клеткиА₁B₁. Запасы первого поставщика полностью израсходованы, по этому остальные клетки первой строки прочеркиваем. ПотребностиВостались неудовлетворенными на200–100=100 ед.Сравниваем этот остаток с запасами поставщикаА₂:так как100<250, то100ед. записываем в клеткуА₂ .B₁, чем полностью удовлетворяем потребности потребителяB₁, а оставшиеся клетки в первом столбце прочеркиваем.

Таблица 2.3

У поставщика А₂осталось150ед. груза. Удовлетворяем потребителяB₂за счет оставшегося у поставщикаА₂груза. Для этого сравниваем этот остаток с потребностями потребителяB₂: 150<200, записываем150ед. в клеткуА₂B₂и, так как запасыА₂полностью израсходованы, прочеркиваем остальные клетки второй строки. ПотребностиB₂остались неудовлетворенными на50ед. Удовлетворяем их за счет поставщикаА₃и переходим к удовлетворениюB₃за счет остатка, имеющегося у поставщикаА₃, и т. д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного плана заканчивается. Таким образом, в табл. в правых верхних углах клеток стоят числа, определяющие стоимость перевозки единицы грузов, а в левых нижних углах — числа, определяющие план перевозок, так как их сумма по строкам равна запасам соответствующего поставщика, а сумма по столбцам — потребности соответствующего потребителя. Проверим, является ли план, построенный втабл. 2.2, опорным. Видим, что, начиная движение от занятой клетки A1B1, вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым ячейкам, невозможно. Следовательно, план является опорным. В то же время план невырожденный, так как содержит точноm + n -1 = 4 + 5 - 1 = 8занятых клеток. При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях-с помощью ЭВМ. Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же ячейках:Z = 100 *10 + 100*2 + 150 *7+ 50 *5 + 100*3 + 50*2 + 50*16+ 250*13 = 6950 (eд. стоимости) Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то, очевидно, план будет значительно ближе к оптимальному.

Пример 2.6.1

Метод минимальной стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, илиb_j . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Составим с помощью этого метода опорный план уже рассмотренной задачи. Запишем ее условие в таблицу (табл. 2.5). Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клеткеA₁,B₄ ) так какA₁=b₄,100ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клеткеA₂ , B₁и в клеткеA₃ , B₅. Заполняем любую из них, напримерA₂ , B₁. Имеем200 < 250, следовательно, записываем в нее200и исключаем из рассмотрения столбецB₁. В клеткуA₃ , B₅записываем200ед. и исключаем из рассмотрения строкуA₃ . В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. В результате получен планX = (X₁₄ = 100; X₂₁ = 200; X₂₂ = 50; X₃₅= 200, X₄₂ = 150; X₄₃ = 100; X₄₅ = 50), остальные значения переменных равны нулю.

Таблица 2.5

План не содержит циклов и состоит из семи положительных перевозок, следовательно, является вырожденным опорным планом. Определим его стоимость: Z = 100*1+200*2+50*7+200*2+150*8+100*12+50*13= 4300 (ед) Стоимость плана перевозок значительно меньше, следовательно, он ближе к оптимальному.

Пример 2.6.2

Метод аппроксимации Фогеля

Данный метод состоит в следующем:

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

находят max Δc_ijи заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

Процесс продолжается до тех пор, пока все грузы не будут развезены по потребителям. Данный метод в ряде задач приводит к оптимальному плану. Решим этим методом задачу из примера 2.6.1(см. табл.2.7).

Таблица 2.7

На первом шаге заполняем клетку A₃ B₁ (max Δc = 5 иmin c_ij = 6), исключаем 1-ый столбец, отметив в дополнительной строке буквой «В» факт выполнения заказа пунктаB₁ . Находим новые разности минимальных тарифов по строкам (в столбцах они не изменились) иmax Δc = 2 в 1-ой строке и в 4-ом столбце. Заполняем клеткуA₁B₄и исключаем 4-й столбец и т.д. В конце остается последовательно заполнить клетки 3-го столбца остатками запасов вA₁ , A₃ ,A₂ . Составленный опорный план дает значениеZ₃ = 909 < Z₂.

Метод двойного предпочтения

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

 

 

16. Оптимизация транспортной задачи методом потенциалов.

 

1.12. Пример решения транспортной задачи методом потенциалов

	1	2	3
1	3	8	2	35
2	7	4	8	30
	15	20	30	=

Опорный план этой задачи найден методом северо-западного угла.

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

Из условий в базисных клетках получаем систему уравнений:

Полагая , находим последовательно платежи и псевдостоимости для свободных клеток. Получаем таб-лицу

	1	2	3
1	3 15	8 [-] 20	12 2 [+]	35	0
2	-1 7	4 [+] 0	8 [-] 30	30	-4
	15	20	30	=
	3	8	12

Стоимость перевозок по плану этой таблицы

.

Так как клетка (1,3) имеет отрицательную цену , то план не является оптимальным. Строим для клетки(1,3) цикл. Цена цикла . По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1,2) не стали отрицательными). При этом стоимость плана изменяется на . Для нового плана вычисляем новые значения платежей и псевдостоимостей:

	1	2	3
1	3 [-] 15	-2 8	2 [+] 20	35	0
2	9 7 [+]	4 20	8 [-] 10	30	6
	15	20	30	=
	3	-2	2

Стоимость перевозок по плану этой таблицы

.

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

	1	2	3
1	3 5	0 8	2 30	35	0
2	7 10	4 20	5 8	30	4
	15	20	30	=
	3	0	2

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

.

2. Задания для практических занятий

2.1. Привести задачу ЛП к канонической форме

2.2. Решить задачу ЛП графически

(во всех заданиях )

2.3. Определить допустимое базисное решение методом

искусственного базиса (во всех заданиях )

2.4. Решить задачу ЛП симплекс-методом

(во всех заданиях )

2.5. Решить задачу ЛП двойственным симплекс-методом

(во всех заданиях )

2.6. Определить задачу, двойственную к исходной

2.7. Используя теоремы двойственности, решить исходную и двойственную задачи (во всех заданиях )

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

(во всех заданиях )

.9. Решить задачу ЦЛП методом Гомори

(во всех заданиях )

2.10. Решить транспортную задачу методом потенциалов

1.							2.
12	6	29	19	21	13		4	21	12	8	1	21
14	3	30	10	10	27		20	8	25	15	23	21
15	27	28	11	24	16		17	1	11	5	3	23
1	23	26	15	13	14		23	10	24	6	5	23
14	14	14	14	14			22	22	22	11	11
3.							4.
5	3	24	10	25	24		21	19	11	12	12	24
30	2	22	16	7	15		26	29	14	1	26	12
30	24	27	29	10	16		39	1	22	8	25	18
15	17	21	2	3	24		53	20	40	26	28	16
12	13	15	15	24			11	13	26	10	10
5.							6.
25	28	20	15	7	16		14	25	18	19	23	33
27	5	11	23	10	12		2	17	16	24	2	25
1	25	14	16	16	14		29	3	7	15	22	25
8	6	4	16	18	18		5	20	17	23	10	17
7	8	4	11	30			33	11	11	11	34
7.							8.
8	1	19	1	15	18		6	6	5	7	17	16
8	27	30	7	7	23		15	8	9	6	23	10
10	20	19	26	20	17		3	14	19	4	20	24
18	28	25	7	22	22		16	13	11	12	2	60
21	21	9	9	20			29	5	35	31	10

 

9.							10.
11	10	15	8	7	16		0	11	2	4	6	15
12	14	29	20	20	15		1	8	7	5	13	9
18	7	5	25	27	24		14	6	9	3	5	11
24	4	30	24	26	15		10	14	16	15	17	25
15	15	15	15	10			10	5	4	21	20
11.							12.
3	18	22	7	1	35		5	13	1	2	6	40
15	2	24	20	4	40		28	3	30	12	30	35
27	3	7	5	11	15		1	8	22	20	27	25
12	28	8	30	31	25		4	17	15	24	19	10
32	28	14	16	25			20	12	18	50	10

 

13.							14.
6	1	8	14	5	10		3	2	22	5	13	23
19	27	3	8	18	4		15	1	21	8	4	20
9	2	4	6	5	12		15	12	24	25	5	26
11	6	9	12	29	8		8	9	20	1	2	16
6	9	5	5	9			15	10	18	30	12

 

15.							16.
1	3	3	1	2	10		29	1	2	1	19	30
10	4	8	3	11	20		28	31	8	30	10	10
20	6	9	1	8	30		15	4	10	20	21	45
4	20	10	17	6	40		25	28	16	5	22	15
15	25	10	20	30			10	15	35	30	20

 

17.							18.
5	1	8	13	3	15		8	6	10	20	3	15
4	8	1	2	6	8		7	1	8	11	9	15
10	20	24	15	16	21		3	4	5	17	21	15
18	17	12	7	6	19		8	9	14	23	16	10
11	9	10	13	20			13	27	5	7	3

 

19.							20.
17	10	21	11	8	24		3	5	30	18	22	16
24	13	10	10	19	20		13	4	29	11	9	10
9	12	27	16	20	11		14	28	27	12	23	24
9	4	4	10	11	11		2	22	27	14	14	60
21	12	10	14	9			29	5	35	31	10
21.							22.
7	2	3	11	20	20		2	4	3	8	1	24
4	8	13	15	6	20		19	18	10	7	5	16
3	7	10	20	31	20		14	12	20	6	11	15
13	14	8	10	11	22		13	7	17	16	21	24
22	10	16	14	20			24	15	15	13	12

 

23.							24.
7	15	6	19	17	6		3	1	2	4	3	10
14	8	17	3	9	26		1	2	4	5	6	5
5	13	11	4	22	20		7	9	12	3	5	5
27	28	1	20	5	23		10	12	8	11	10	10
12	30	18	10	15			10	5	5	5	5

 

25.							26.
2	4	1	3	6	35		5	3	8	49	32	80
7	9	8	11	7	10		28	4	14	27	7	10
4	1	2	5	6	18		81	15	16	10	25	40
5	3	9	7	8	17		30	9	20	64	2	20
15	3	30	12	20			15	70	17	5	43
27.							28.
6	6	3	7	17	16		12	6	28	19	21	14
15	8	9	6	23	10		14	3	30	10	10	16
3	14	19	4	20	24		15	27	28	11	24	27
16	13	11	12	2	60		1	23	26	15	13	13
29	5	35	31	10			14	14	14	14	14
29.							30.
1	19	4	15	6	19		10	2	4	1	11	3
22	8	14	3	21	21		3	12	13	2	8	16
5	30	11	12	7	8		1	8	3	4	7	7
6	17	24	23	9	15		2	7	5	3	20	13
20	13	10	9	11			4	14	5	14	2

 

---

Дата добавления: 2019-01-14; просмотров: 1512; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!